Extended Formulations in Combinatorial Optimization

2011/04/06 by Volker Kaibel, Kaibel, Volker · 29 citations
Computer Science · Engineering · Mathematics · #52B12 #90C10 #90C57 #Advanced Graph Theory Research #Algorithm #Combinatorial optimization #Combinatorics #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Computer science #FOS: Mathematics #Mathematical optimization #Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Optimization problem #Polyhedron #Polytope #Projection (relational algebra) #Sketch #Theoretical computer science #math.CO #math.OC #msc:52B12 #msc:90C10 #msc:90C57

paper · pdf · doi:10.48550/arxiv.1104.1023

published in arXiv (Cornell University) (Cornell University) · 14 pages, 1 figure; Optima 85, 2011

arxiv created 2011/04/06 · openalex publication_date 2011/04/06 · arxiv updated 2011/04/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The concept of representing a polytope that is associated with some combinatorial optimization problem as a linear projection of a higher-dimensional polyhedron has recently received increasing attention. In this paper (written for the newsletter Optima of the Mathematical Optimization Society), we provide a brief introduction to this topic and sketch some of the recent developments with respect to both tools for constructing such extended formulations as well as lower bounds on their sizes.

Cited by

• Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
• Extended formulations for induced tree and path polytopes of chordal graphs
• Extended formulations for the maximum weighted co-2-plex problem
• A Unified and Scalable Method for Optimization over Graphs of Convex Sets
• A combinatorial approach to Ramana's exact dual for semidefinite programming
• An unconditional lower bound for the active-set method in convex quadratic maximization
• On the Importance of Studying the Membership Problem for Pedigree Polytopes
• ModelEquivBench: Certifying Multi-Relational Evaluation of LLM-Generated Optimization Models
• Bregman Conditional Random Fields: Sequence Labeling with Parallelizable Inference Algorithms
• Linear vs. semidefinite extended formulations
• Positive Semidefinite Matrix Factorization: A Connection With Phase Retrieval and Affine Rank Minimization
• A Special Role of Boolean Quadratic Polytopes among Other Combinatorial Polytopes
• Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes

Related

• Combinatorial Bounds on Nonnegative Rank and Extended Formulations
• Finding Descriptions of Polytopes via Extended Formulations and Liftings
• Constructing Extended Formulations from Reflection Relations
• Some Algorithmic Problems in Polytope Theory
• Optimality conditions and complete description of polytopes in combinatorial optimization