Extended formulations in combinatorial optimization
From MaRDI portal
Publication:5919994
DOI10.1007/s10479-012-1269-0zbMath1273.90170OpenAlexW2337855014MaRDI 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
Related Items
Lifting for Simplicity: Concise Descriptions of Convex Sets, Integrality gaps for strengthened linear relaxations of capacitated facility location, Improved compact formulations for metric and cut polyhedra, Extension complexity of low-dimensional polytopes, Extension complexities of Cartesian products involving a pyramid, On the extension complexity of scheduling polytopes, Solving the Distance-Based Critical Node Problem, Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes, Extended formulations for matroid polytopes through randomized protocols, Polytopes associated with symmetry handling, Lifts for Voronoi cells of lattices, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, A strong formulation for the graph partition problem, The Polyhedral Geometry of Pivot Rules and Monotone Paths, Efficient MIP techniques for computing the relaxation complexity, Packing, partitioning, and covering symresacks, The role of rationality in integer-programming relaxations, Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes, On permuting some coordinates of polytopes, Computational aspects of relaxation complexity: possibilities and limitations, Extended formulation for CSP that is compact for instances of bounded treewidth, Maximum semidefinite and linear extension complexity of families of polytopes, Fooling sets and the spanning tree polytope, Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives, Unnamed Item, Cutting planes from extended LP formulations, Circuit and bond polytopes on series-parallel graphs, Extended formulations for vertex cover, Extension complexity of the correlation polytope, Extended formulations for radial cones, Realizability of polytopes as a low rank matrix completion problem, Recognizing Cartesian products of matrices and polytopes, Extension complexity of formal languages, Semidefinite Descriptions of the Convex Hull of Rotation Matrices
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
