We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP) that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show ...
详细信息
We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP) that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in [D. Cvetkovic, M. Cangalovic, and V. Kovacevic-Vujcic, Semidefinite programming methods for the symmetric traveling salesman problem, in Proceedings of the 7thinternationalipcoconference on integerprogramming and combinatorialoptimization, Springer-Verlag, London, UK, 1999, pp. 126-136]. Unlike the bound of Cvetkovic et al., the new SDP bound is not dominated by the Held-Karp linear programming bound, or vice versa.
We start with definitions given by Plotkin, Shmoys, and Tardos [16]. Given A∈?m×n, b∈?m and a polytope P $
 \subseteq$
 \subseteq ? n , the fractional packing problem is to find an x ∈ P such t...
ISBN:
(纸本)3540660194
We start with definitions given by Plotkin, Shmoys, and Tardos [16]. Given A∈?m×n, b∈?m and a polytope P $
\subseteq$
\subseteq ? n , the fractional packing problem is to find an x ∈ P such that Ax ≤ b if such an x exists. An ∈-approximate solution to this problem is an x ∈ P such that Ax ≤ (1+∈)b. An ∈-relaxed decision procedure always finds an ∈-approximate solution if an exact solution exists.
We study the problem of optimizing over the set of all combinatorial embeddings of a given planar graph. Our objective function prefers certain cycles of G as face cycles in the embedding. the motivation for studying ...
详细信息
ISBN:
(纸本)3540660194
We study the problem of optimizing over the set of all combinatorial embeddings of a given planar graph. Our objective function prefers certain cycles of G as face cycles in the embedding. the motivation for studying this problem arises in graph drawing, where the chosen embedding has an important influence on the aesthetics of the drawing. We characterize the set of all possible embeddings of a given biconnected planar graph G by means of a system of linear inequalities with {0, 1}-variables corresponding to the set of those cycles in G which can appear in a combinatorial embedding. this system of linear inequalities can be constructed recursively using SPQR-trees and a new splitting operation. Our computational results on two benchmark sets of graphs are surprising: the number of variables and constraints seems to grow only linearly withthe size of the graphs although the number of embeddings grows exponentially. For all tested graphs (up to 500 vertices) and linear objective functions, the resulting integer linear programs could be generated within 10 minutes and solved within two seconds on a Sun Enterprise 10000 using CPLEX.
We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick lineari...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146-152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, we complement Khajavirad's result by showing that the intersection of the relaxations of such linearizations and the extended flower relaxation are equally strong.
the Chvatal rank of an inequality ax less than or equal to b with integral components and valid for the integral hull of a polyhedron P, is the minimum number of rounds of Gomory-Chvatal cutting planes needed to obtai...
详细信息
ISBN:
(数字)9783540487777
ISBN:
(纸本)3540660194
the Chvatal rank of an inequality ax less than or equal to b with integral components and valid for the integral hull of a polyhedron P, is the minimum number of rounds of Gomory-Chvatal cutting planes needed to obtain the given inequality. the Chvatal rank is st most one if b is the integral part of the optimum value z(a) of the linear program max{ax : x is an element of P}. We show that, contrary to what was stated or implied by other authors, the converse to the latter statement, namely, the Chvatal rank is at least two if b is less than the integral part of z(a), is not true in general. We establish simple conditions for which this implication is valid, and apply these conditions to several classes of facet-inducing inequalities for travelling salesman polytopes.
We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral con...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral cones can sometimes have a notion of finite generating set. We show this is true for the cone of positive semidefinite matrices (PSD) and the second-order cone (SOC). Both cones have a finite generating set of integer points, similar in spirit to Hilbert bases, under the action of a finitely generated group. We also extend notions of total dual integrality, Gomory-Chv ' atal closure, and Carath ' eodory rank to integer points in arbitrary cones.
作者：
Sebo, ACNRS
Lab Leibniz IMAG Grenoble France Kyoto Univ
Math Sci Res Inst Kyoto 60601 Japan
We study simplices whose vertices lie on a lattice and have no other lattice points. Such 'empty lattice simplices' come up in the theory of integerprogramming, and in some combinatorial problems. they have b...
详细信息
ISBN:
(纸本)3540660194
We study simplices whose vertices lie on a lattice and have no other lattice points. Such 'empty lattice simplices' come up in the theory of integerprogramming, and in some combinatorial problems. they have been investigated in various contexts and under varying terminology by Reeve, White, Scarf, Kannan and Lovasz, Reznick, Kantor, Naase and Ziegler, etc. Can the 'emptiness' of lattice simplices be 'well-characterized' ? Is their 'lattice-width' small ? Do the integer points of the parallelepiped they generate have a particular structure ? the 'good characterization' of empty lattice simplices occurs to be open in general ! We provide a polynomial algorithm for deciding when a given integer 'knapsack' or 'partition' lattice simplex is empty. More generally, we ask for a characterization of linear inequalities satisfied by the lattice points of a lattice parallelepiped. We state a conjecture about such inequalities, prove it for n less than or equal to 4, and deduce several variants of classical results of Reeve, White and Scarf characterizing the emptiness of small dimensional lattice simplices. For instance, a three dimensional integer simplex is empty if and only if all its faces have width 1. Seemingly different characterizations can be easily proved from one another using the Hermite normal form. In fixed dimension the width of polytopes can be computed in polynomial time (see the simple integerprogramming formulation of Naase and Ziegler). We prove that it is already NP-complete to decide whether the width of a very special class of integer simplices is 1, and we also provide for every n greater than or equal to 3 a simple example of n-dimensional empty integer simplices of width n - 2, improving on earlier bounds.
In this paper we consider a variant of the betweenness problem occurring in computational biology. We present a new polyhedral approach which incorporates the solution of consecutive ones problems and show that it sup...
详细信息
ISBN:
(纸本)354064590X
In this paper we consider a variant of the betweenness problem occurring in computational biology. We present a new polyhedral approach which incorporates the solution of consecutive ones problems and show that it supersedes an earlier one. A particular feature of this new branch-and-cut algorithm is that it is not based on an explicit integerprogramming formulation of the problem and makes use of automatically generated facet-defining inequalities.
暂无评论