Constructing Extended Formulations from Reflection Relations

DOI10.1007/978-3-642-20807-2_23zbMath1341.90148OpenAlexW1826659920MaRDI QIDQ3009770

Volker Kaibel, Kanstantsin Pashkovich

Publication date: 24 June 2011

Published in: Integer Programming and Combinatoral Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20807-2_23

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items

Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies, Sparse sums of squares on finite abelian groups and improved semidefinite lifts, Extension complexity of low-dimensional polytopes, Extension complexities of Cartesian products involving a pyramid, Polytopes of minimum positive semidefinite rank, Simple extensions of polytopes, On permuting some coordinates of polytopes, Unnamed Item, Deriving compact extended formulations via LP-based separation techniques, On the linear description of the Huffman trees polytope, On the linear extension complexity of regular \(n\)-gons, Deriving compact extended formulations via LP-based separation techniques, Extended formulations in combinatorial optimization, Extended formulations for polygons, Polyhedral approximation of ellipsoidal uncertainty sets via extended formulations: a computational case study, Mixed Integer Linear Programming Formulation Techniques, Balas formulation for the union of polytopes is optimal, Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results, An upper bound for nonnegative rank, Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis, The projected faces property and polyhedral relations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smallest compact formulation for the permutahedron
• Sorting in \(c \log n\) parallel steps
• Expressing combinatorial optimization problems by linear programs
• Structure of a simple scheduling polyhedron
• Polyhedral Characterization of Discrete Dynamic Programming
• Symmetry Matters for the Sizes of Extended Formulations
• Branched Polyhedral Systems
• On Polyhedral Approximations of the Second-Order Cone
• Extended formulations in combinatorial optimization