On the general routing polytope

The General Routing Problem (GRP) consists of finding a minimum length closed walk in an edge-weighted undirected graph, subject to containing certain sets of required nodes and edges. It is related to the Rural Postman Problem and the Graphical Traveling Salesman Problem.We examine the 0/1-polytope associated with the GRP introduced by Ghiani and Laporte [A branch-and-cut algorithm for the Undirected Rural Postman Problem, Math. Program. Ser. A 87 (3) (2000) 467-481]. We show that whenever it is not full-dimensional, the set of equations and facets can be characterized, and the polytope is isomorphic to the full-dimensional polytope associated with another GRP instance which can be obtained in polynomial time. We also offer a node-lifting method. Both results are applied to prove the facet-defining property of some classes of valid inequalities. As a tool, we study more general polyhedra associated to the GRP.     

A branch-and-cut algorithm for the Undirected Rural Postman Problem

The well-known Undirected Rural Postman Problem is considered and a binary linear problem using new dominance relations is presented. Polyhedral properties are investigated and a branch-and-cut algorithm is developed. Extensive computational results indicate that the algorithm is capable of solving much larger instances than previously reported. Received: December 1, 1997 / Accepted: October 13, 1999?Published online January 27, 2000     

A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem

This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.?First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP. Received: September 5, 1997 / Accepted: November 15, 1999?Published online February 23, 2000     

The mathematics of playing golf, or: a new class of difficult non-linear mixed integer programs

We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with k=1 and k=2, every optimal solution is integral. In contrast to this, for every k≥3 there exist instances where every optimal solution takes non-integral values. Received: August 2001 / Accepted: January 2002?Published online March 27, 2002     

Diophantine definability over non-finitely generated non-degenerate modules of algebraic extensions of ℚ

We investigate the issues of Diophantine definability over the non-finitely generated version of non-degenerate modules contained in the infinite algebraic extensions of the rational numbers. In particular, we show the following. Let k be a number field and let K _inf be a normal algebraic, possibly infinite, extension of k such that k has a normal extension L linearly disjoint from K _inf over k. Assume L is totally real and K _inf is totally complex. Let M _inf be a non-degenerate O _k -module, possibly non-finitely generated and contained in O _Kinf . Then M _inf contains a submodule Mˉ _inf such that M _inf /Mˉ _inf is torsion and O _k has a Diophantine definition over Mˉ _inf . Received: 4 May 1999 / Published online: 21 March 2001     

Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization

Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c ^T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations. Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000     

An improved rounding method and semidefinite programming relaxation for graph partition

Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming (SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut, and Max-Vertex-Cover. Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Green functions and eigenfunction expansions for the square of the Laplace–Beltrami operator on plane domains

For a certain class of domains Ω⊂ℂ with smooth boundary and Δtilde;_Ω=w ²Δ the Laplace–Beltrami operator with respect to the Poincaré metric ds ²=w(z)^-2 dz dz on Ω, we (1) show that the Green function for the biharmonic operator Δtilde;_Ω ², with Dirichlet boundary data, is positive on Ω×Ω; and (2) obtain an eigenfunction expansion for the operator Δtilde;_Ω, which reduces to the ordinary non-Euclidean Fourier transform of Helgason for Ω=𝔻 (the unit disc). In both cases the proofs go via uniformization, and in (1) we obtain a Myrberg-like formula for the corresponding Green function. Finally, the latter formula as well as the eigenfunction expansion are worked out more explicitly in the simplest case of Ω an annulus, and a result is established concerning the convergence of the series ∑ _ω∈G (1-|ω0|²) ^s for G the covering group of the uniformization map of Ω and 0<s<1. Received: August 21, 2000?Published online: October 30, 2002 RID="*" ID="*"The first author was supported by GA AV CR grants no. A1019701 and A1019005.     

A polynomial dual simplex algorithm for the generalized circulation problem

This paper presents a polynomial-time dual simplex algorithm for the generalized circulation problem. An efficient implementation of this algorithm is given that has a worst-case running time of O(m ²(m+nlogn)logB), where n is the number of nodes, m is the number of arcs and B is the largest integer used to represent the rational gain factors and integral capacities in the network. This running time is as fast as the running time of any combinatorial algorithm that has been proposed thus far for solving the generalized circulation problem. Received: June 1998 / Accepted: June 27, 2001?Published online September 17, 2001     

A continuation theorem with applications to periodically forced Liénard equations in the presence of a separatrix

In this paper we prove a result on the existence of periodic motions for the periodically forced Liénard differential equation x ^″+f(x)x ^′+g(x)=e(t) in a situation where the phase portrait of the associated autonomous equation is similar to that of a centre limited by an unbounded separatrix. The existence result, which is based on a degree theoretic continuation theorem, enables us to treat some interesting cases not previously considered in the literature. Received: April 27, 2000 Published online: December 19, 2001     

Convergence and efficiency of subgradient methods for quasiconvex minimization

We study a general subgradient projection method for minimizing a quasiconvex objective subject to a convex set constraint in a Hilbert space. Our setting is very general: the objective is only upper semicontinuous on its domain, which need not be open, and various subdifferentials may be used. We extend previous results by proving convergence in objective values and to the generalized solution set for classical stepsizes t _k →0, ∑t _k =∞, and weak or strong convergence of the iterates to a solution for {t _k }∈ℓ₂∖ℓ₁ under mild regularity conditions. For bounded constraint sets and suitable stepsizes, the method finds ε-solutions with an efficiency estimate of O(ε^-2), thus being optimal in the sense of Nemirovskii. Received: October 4, 1998 / Accepted: July 24, 2000?Published online January 17, 2001     

Extension of locally pseudocompact group actions

It is shown that: (1) any action of a Moscow group G on a first countable, Dieudonné complete (in particular, on a metrizable) space X can uniquely be extended to an action of the Dieudonné completion γG on X, (2) any action of a locally pseudocompact topological group G on a b _f -space (in particular, on a first countable space) X can uniquely be extended to an action of the Weil completion on the Dieudonné completion γX of X. As a consequence, we obtain that, for each locally pseudocompact topological group G, every G-space with the b _f -property admits an equivariant embedding into a compact Hausdorff G-space. Furthermore, for each pseudocompact group G, every metrizable G-space has a G-invariant metric compatible with its topology. We also give a direct construction of such an invariant metric. Received: June 22, 2000; in final form: May 22, 2001?Published online: June 11, 2002     

Self-regular functions and new search directions for linear and semidefinite optimization

In this paper, we introduce the notion of a self-regular function. Such a function is strongly convex and smooth coercive on its domain, the positive real axis. We show that any such function induces a so-called self-regular proximity function and a corresponding search direction for primal-dual path-following interior-point methods (IPMs) for solving linear optimization (LO) problems. It is proved that the new large-update IPMs enjoy a polynomial ?(n log) iteration bound, where q≥1 is the so-called barrier degree of the kernel function underlying the algorithm. The constant hidden in the ?-symbol depends on q and the growth degree p≥1 of the kernel function. When choosing the kernel function appropriately the new large-update IPMs have a polynomial ?(lognlog) iteration bound, thus improving the currently best known bound for large-update methods by almost a factor . Our unified analysis provides also the ?(log) best known iteration bound of small-update IPMs. At each iteration, we need to solve only one linear system. An extension of the above results to semidefinite optimization (SDO) is also presented. Received: March 2000 / Accepted: December 2001?Published online April 12, 2002     

Boolean deductive systems of BL-algebras

BL-algebras rise as Lindenbaum algebras from many valued logic introduced by Hájek [2]. In this paper Boolean ds and implicative ds of BL-algebras are defined and studied. The following is proved to be equivalent: (i) a ds D is implicative, (ii) D is Boolean, (iii) L/D is a Boolean algebra. Moreover, a BL-algebra L contains a proper Boolean ds iff L is bipartite. Local BL-algebras, too, are characterized. These results generalize some theorems presented in [4], [5], [6] for MV-algebras which are BL-algebras fulfiling an additional double negation law x = x ^**. Received: 22 June 1998 /?Published online: 18 May 2001     

A fast algorithm for computing minimum 3-way and 4-way cuts

For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n ^k-1 F(n,m))=O(mn ^k log(n ² /m)) time and O(n ²) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn ³) for weighted graphs, but improves the bound ?(mn ³) to O(n ² F(n,m))=O(min{mn ^8/3,m ^3/2 n ²}) for unweighted graphs. The bound ?(mn ⁴) for k=4 improves the previous best randomized bound ?(n ⁶) (for m=o(n ²)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. Received: April 1999 / Accepted: February 2000?Published online August 18, 2000     

On the rank of mixed 0,1 polyhedra

For a polytope in the [0,1] ⁿ cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n ²logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables. Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001     

Chtoucas de Drinfeld et correspondance de Langlands

One proves Langlands’ correspondence for GL _r over function fields. This is a generalization of Drinfeld’s proof in the case of rank 2 : Langlands’ correspondence is realized in ℓ-adic cohomology spaces of the modular varieties classifying rank r Drinfeld shtukas. Oblatum 13-X-2000 & 7-VI-2001?Published online: 12 October 2001     

On semidefinite linear complementarity problems

Given a linear transformation L:? ⁿ →? ⁿ and a matrix Q∈? ⁿ , where ? ⁿ is the space of all symmetric real n×n matrices, we consider the semidefinite linear complementarity problem SDLCP(L,? ⁿ ₊,Q) over the cone ? ⁿ ₊ of symmetric n×n positive semidefinite matrices. For such problems, we introduce the P-property and its variants, Q- and GUS-properties. For a matrix A∈R ^n×n , we consider the linear transformation L _A :? ⁿ →? ⁿ defined by L _A (X):=AX+XA ^T and show that the P- and Q-properties for L _A are equivalent to A being positive stable, i.e., real parts of eigenvalues of A are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov. Received: March 1999 / Accepted: November 1999?Published online April 20, 2000     

Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions

In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an O( logε^-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh, Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms for SOCP based on this search direction. Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000     

On convergence of the Gauss-Newton method for convex composite optimization

The local quadratic convergence of the Gauss-Newton method for convex composite optimization f=h∘F is established for any convex function h with the minima set C, extending Burke and Ferris’ results in the case when C is a set of weak sharp minima for h. Received: July 24, 1998 / Accepted: November 29, 2000?Published online September 3, 2001