On cardinality constrained cycle and path polytopes

Given a directed graph D = (N, A) and a sequence of positive integers ${1 \leq c_1 < c_2 < \cdots < c_m \leq |N|}Given a directed graph D = (N, A) and a sequence of positive integers 1 ￡ c₁ < c₂ < ? < c_m ￡ |N|{1 \leq c_1 < c_2 < \cdots < c_m \leq |N|}, we consider those path and cycle polytopes that are defined as the convex hulls of the incidence vectors simple paths and cycles of D of cardinality c _p for some p ? {1,?,m}{p \in \{1,\ldots,m\}}, respectively. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. These inequalities can simply be transformed into inequalities that characterize the integer points of the undirected counterparts of cardinality constrained path and cycle polytopes. Beyond we investigate some further inequalities, in particular inequalities that are specific to odd/even paths and cycles.     

Which nonnegative matrices are slack matrices?

In this paper we characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack matrix. The underlying decision problem is equivalent to the polyhedral verification problem whose complexity is unknown.     

Special Issue: International Symposium on Mathematical Programming 2022

Mathematical Programming -     

Computing the face lattice of a polytope from its vertex-facet incidences

We give an algorithm that constructs the Hasse diagram of the face lattice of a convex polytope P from its vertex-facet incidences in time O(min{n,m}··), where n is the number of vertices, m is the number of facets, is the number of vertex-facet incidences, and  is the total number of faces of P. This improves results of Fukuda and Rosta [Computational Geometry 4 (4) (1994) 191–198], who described an algorithm for enumerating all faces of a d-polytope in O(min{n,m}·d·²) steps. For simple or simplicial d-polytopes our algorithm can be specialized to run in time O(d··). Furthermore, applications of the algorithm to other atomic lattices are discussed, e.g., to face lattices of oriented matroids.     

Box-inequalities for quadratic assignment polytopes

Linear Programming based lower bounds have been considered both for the general as well as for the symmetric quadratic assignment problem several times in the recent years. Their quality has turned out to be quite good in practice. Investigations of the polytopes underlying the corresponding integer linear programming formulations (the non-symmetric and the symmetric quadratic assignment polytope) have been started during the last decade [34, 31, 21, 22]. They have lead to basic knowledge on these polytopes concerning questions like their dimensions, affine hulls, and trivial facets. However, no large class of (facet-defining) inequalities that could be used in cutting plane procedures had been found. We present in this paper the first such class of inequalities, the box inequalities, which have an interesting origin in some well-known hypermetric inequalities for the cut polytope. Computational experiments with a cutting plane algorithm based on these inequalities show that they are very useful with respect to the goal of solving quadratic assignment problems to optimality or to compute tight lower bounds. The most effective ones among the new inequalities turn out to be indeed facet-defining for both the non-symmetric as well as for the symmetric quadratic assignment polytope. Received: April 17, 2000 / Accepted: July 3, 2001?Published online September 3, 2001