Compact vs. exponential-size LP relaxations
From MaRDI portal
The authors illustrate by means of examples a technique for formulating compact (polynomial-size) linear programming relaxations in place of exponential-size models requiring separation algorithms. They state the equivalence of compact separation and compact optimization. They also introduce a new formulation for the traveling salesman problem whose relaxation is equivalent to subtour elimination relaxation.
Recommendations
- Deriving compact extended formulations via LP-based separation techniques
- Deriving compact extended formulations via LP-based separation techniques
- A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
- Compact extended linear programming models
- The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
Cites work
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
- Exact algorithms for minimum routing cost trees
- Expressing combinatorial optimization problems by linear programs
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- scientific article; zbMATH DE number 1102774 (Why is no real title available?)
- Network flows. Theory, algorithms, and applications.
- Optimum Communication Spanning Trees
- The ellipsoid method and its consequences in combinatorial optimization
- Using separation algorithms to generate mixed integer model reformulations
Cited in
(21)- Compact extended linear programming models
- Compact optimization can outperform separation: a case study in structural proteomics
- New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
- Learning to classify with missing and corrupted features
- A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
- A branch-and-cut algorithm for multiple sequence alignment
- Mixed integer linear programming formulation techniques
- An effective compact formulation of the max cut problem on sparse graphs
- A method for the construction of relaxations of polytopes generated by subgroups of the symmetric group
- DC programming and DCA for challenging problems in bioinformatics and computational biology
- On Fault-Tolerant Low-Diameter Clusters in Graphs
- Integer Programming Formulations for Minimum Spanning Tree Interdiction
- Deriving compact extended formulations via LP-based separation techniques
- A new integer programming formulation of the graphical traveling salesman problem
- Deriving compact extended formulations via LP-based separation techniques
- A new integer programming formulation of the graphical traveling salesman problem
- An extended formulation for the 1‐wheel inequalities of the stable set polytope
- Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
- New formulations of the multiple sequence alignment problem
- A time-indexed LP-based approach for min-sum job-shop problems
- Characterization of facets of the hop constrained chain polytope via dynamic programming
This page was built for publication: Compact vs. exponential-size LP relaxations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1612003)
