Extended formulations in combinatorial optimization
From MaRDI portal
Publication:5919994
DOI10.1007/s10479-012-1269-0zbMath1273.90170MaRDI QIDQ5919994
Michele Conforti, Cornuéjols, Gérard, Giacomo Zambelli
Publication date: 8 August 2013
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-012-1269-0
90C27: Combinatorial optimization
Related Items
Lifting for Simplicity: Concise Descriptions of Convex Sets, Extension complexity of low-dimensional polytopes, Solving the Distance-Based Critical Node Problem, Semidefinite Descriptions of the Convex Hull of Rotation Matrices, Lifts for Voronoi cells of lattices, The Polyhedral Geometry of Pivot Rules and Monotone Paths, Efficient MIP techniques for computing the relaxation complexity, On permuting some coordinates of polytopes, Integrality gaps for strengthened linear relaxations of capacitated facility location, Improved compact formulations for metric and cut polyhedra, Cutting planes from extended LP formulations, Realizability of polytopes as a low rank matrix completion problem, Extension complexity of formal languages, Extended formulation for CSP that is compact for instances of bounded treewidth, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Maximum semidefinite and linear extension complexity of families of polytopes, Fooling sets and the spanning tree polytope, Circuit and bond polytopes on series-parallel graphs, Extended formulations for vertex cover, Recognizing Cartesian products of matrices and polytopes, Packing, partitioning, and covering symresacks, Extension complexity of the correlation polytope, Extended formulations for radial cones, Extension complexities of Cartesian products involving a pyramid, Polytopes associated with symmetry handling, On the extension complexity of scheduling polytopes, Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes, Extended formulations for matroid polytopes through randomized protocols, Computational aspects of relaxation complexity: possibilities and limitations, Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes, Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tightening simple mixed-integer sets with guaranteed bounds
- On cuts and matchings in planar graphs
- Extended formulations for polygons
- The perfectly matchable subgraph polytope of an arbitrary graph
- Packing and partitioning orbitopes
- Compact formulations as a union of polyhedra
- Approximate formulations for 0-1 knapsack sets
- On stable set polyhedra for K//(1,3)free graphs
- Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus
- Expressing combinatorial optimization problems by linear programs
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- On defining sets of vertices of the hypercube by linear inequalities
- Tight formulations for some simple mixed integer programs and convex objective integer programs
- Polyhedra for lot-sizing with Wagner-Whitin costs
- A characterization of weakly bipartite graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Approximate extended formulations
- Constructing Extended Formulations from Reflection Relations
- The perfectly matchable subgraph polytope of a bipartite graph
- Network Formulations of Mixed-Integer Programs
- Extended Formulations for Packing and Partitioning Orbitopes
- Projecting an Extended Formulation for Mixed-Integer Covers on Bipartite Graphs
- Polyhedral Characterization of Discrete Dynamic Programming
- Polyhedral Approaches to Mixed Integer Linear Programming
- Symmetry Matters for the Sizes of Extended Formulations
- Branched Polyhedral Systems
- On the Complexity of Nonnegative Matrix Factorization
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
- Odd Minimum Cut-Sets and b-Matchings
- On the existence of optimal solutions to integer and mixed-integer programming problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Reducing Matching to Polynomial Size Linear Programming
- Lectures on Polytopes
- Color-coding
- Nondeterministic Quantum Query and Communication Complexities
- Matching, Euler tours and the Chinese postman
- Linear vs. semidefinite extended formulations
- Production Planning by Mixed Integer Programming
- Maximum matching and a polyhedron with 0,1-vertices
- Matroids and the greedy algorithm
- On Polyhedral Approximations of the Second-Order Cone
- The Continuous Mixing Polyhedron
- Extended formulations in combinatorial optimization
- Mixing mixed-integer inequalities
