We establish that the extension complexity of the nXn correlation polytope is at least 1.5^n by a short proof that is self-contained except for using the fact that every face of a polyhedron is the intersection of all facets it is contained in. The main innovative aspect of the proof is a simple combinatorial argument … Read more
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 verifi cation problem whose complexity is unknown. Citation April 2013 Article Download View Which Nonnegative Matrices … Read more
We introduce a natural abstraction of propositional proof systems that are based on cut- ting planes. This leads to a new class of proof systems that includes many well-known meth- ods, such as Gomory-Chvátal cuts, lift-and-project cuts, Sherali-Adams cuts, or split cuts. The rank of a proof system corresponds to the number of rounds that … Read more
We show that there are 0-1 and unbounded knapsack polytopes with super-polynomial extension complexity. More specifically, for each n in N we exhibit 0-1 and unbounded knapsack polyhedra in dimension n with extension complexity \Omega(2^\sqrt{n}). Article Download View A NOTE ON THE EXTENSION COMPLEXITY OF THE KNAPSACK POLYTOPE
The classical single-band uncertainty model introduced by Bertsimas and Sim has represented a breakthrough in the development of tractable robust counterparts of Linear Programs. However, adopting a single deviation band may be too limitative in practice: in many real-world problems, observed deviations indeed present asymmetric distributions over asymmetric ranges, so that getting a higher modeling … Read more
We present a new lifting approach for strengthening arbitrary clique tree inequalities that are known to be facet defining for the symmetric traveling salesman problem in order to get stronger valid inequalities for the symmetric quadratic traveling salesman problem (SQTSP). Applying this new approach to the subtour elimination constraints (SEC) leads to two new classes … Read more
In this paper, we study self-avoiding walks of a given length on a graph. We consider a formulation of this problem as a binary linear program. We analyze the polyhedral structure of the underlying polytope and describe valid inequalities. Proofs for their facial properties for certain special cases are given. In a variation of this … Read more
This paper considers robust dynamic optimization problems, where the unknown parameters are modeled as uncertainty sets. We seek to bridge two classical paradigms for solving such problems, namely (1) Dynamic Programming (DP), and (2) policies parameterized in model uncertainties (also known as decision rules), obtained by solving tractable convex optimization problems. We provide a set … Read more
The positive semidefinite (psd) rank of a polytope is the smallest $k$ for which the cone of $k \times k$ real symmetric psd matrices admits an affine slice that projects onto the polytope. In this paper we show that the psd rank of a polytope is at least the dimension of the polytope plus one, … Read more
We study the computational question whether a given polytope or spectrahedron $S_A$ (as given by the positive semidefiniteness region of a linear matrix pencil $A(x)$) is contained in another one $S_B$. First we classify the computational complexity, extending results on the polytope/poly\-tope-case by Gritzmann and Klee to the polytope/spectrahedron-case. For various restricted containment problems, NP-hardness … Read more