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 (21)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Constructing Extended Formulations from Reflection Relations