Using separation algorithms to generate mixed integer model reformulations
From MaRDI portal
The linear relaxation of mixed integer programming models can be strengthened by introducing auxiliary variables. The author develops a new method for generating auxiliary variable reformulations for problems where the separation algorithm for finding violated cuts can be formulated as a linear program. The results have important consequences for integrality proofs and efficient formulations. Typical examples of the method are graph optimization and fixed charged problems. Computational results for one of the graph optimization problems (a traversal matroid) suggest that the new method is more stable than a conventional cutting plane method in the computational time required.
Recommendations
- Reformulation and decomposition of integer programs
- Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition
- Formulations and Reformulations in Integer Programming
- Solving Mixed Integer Programming Problems Using Automatic Reformulation
- Bilevel programming and the separation problem
Cites work
- A dual ascent approach for steiner tree problems on a directed graph
- A Selection Problem of Shared Fixed Costs and Network Flows
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
- Gainfree Leontief substitution flow problems
- scientific article; zbMATH DE number 3815002 (Why is no real title available?)
- scientific article; zbMATH DE number 3580570 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- Minimum cuts, modular functions, and matroid polyhedra
- Modelling with integer variables
- On cuts and matchings in planar graphs
- On the cut polytope
- Operations that preserve total dual integrality
- Reformulation of the Multiperiod MILP Model for Capacity Expansion of Chemical Processes
- Selected Applications of Minimum Cuts in Networks
- The perfectly matchable subgraph polytope of a bipartite graph
- Trees and Cuts
- Uncapacitated Lot-Sizing Problems with Start-Up Costs
- Uncapacitated lot-sizing: The convex hull of solutions
- Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
- Valid inequalities and separation for uncapacitated fixed charge networks
Cited in
(78)- Strong formulations for mixed integer programming: A survey
- A result on projection for the vehicle routing problem
- The splitting of variables and constraints in the formulation of integer programming models
- Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
- Node packings on cocomparability graphs
- Compact vs. exponential-size LP relaxations
- Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations
- Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods
- Optimal design of switched Ethernet networks implementing the multiple spanning tree protocol
- Fooling sets and the spanning tree polytope
- Valid inequalities for the single arc design problem with set-ups
- Ordered weighted average optimization in multiobjective spanning tree problem
- Subgraph polytopes and independence polytopes of count matroids
- Long range planning in the process industries: A projection approach
- Separation routine and extended formulations for the stable set problem in claw-free graphs
- Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles
- Electrical flows over spanning trees
- Exploring the tradeoffs among forest planning, roads and wildlife corridors: a new approach
- Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
- Certifiably optimal sparse inverse covariance estimation
- Parsimonious formulations for low-diameter clusters
- Extended formulations for radial cones
- On the linear extension complexity of stable set polytopes for perfect graphs
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- A generalization of extension complexity that captures P
- On the combinatorial lower bound for the extension complexity of the spanning tree polytope
- Connected power domination in graphs
- Some \(0/1\) polytopes need exponential size extended formulations
- The k-Track assignment problem on partial orders
- The prize-collecting generalized minimum spanning tree problem
- Polyhedral description of the integer single node flow set with constant bounds
- A branch-and-cut algorithm for multiple sequence alignment
- On the extension complexity of scheduling polytopes
- Improved approaches to solve the one-to-one skewgram problem
- Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
- Extended formulations for matroid polytopes through randomized protocols
- Mixed integer linear programming formulation techniques
- An effective compact formulation of the max cut problem on sparse graphs
- Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
- Extended formulations for sparsity matroids
- New formulations for the elementary shortest-path problem visiting a given set of nodes
- Extended formulations for independence polytopes of regular matroids
- Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition
- Mixed integer linear programming formulations for probabilistic constraints
- Extended formulations of lower-truncated transversal polymatroids
- Sparktope: linear programs from algorithms
- On Fault-Tolerant Low-Diameter Clusters in Graphs
- Intersection Disjunctions for Reverse Convex Sets
- Regular matroids have polynomial extension complexity
- Learning in combinatorial optimization: what and how to explore
- The optimal design of low-latency virtual backbones
- Smaller extended formulations for the spanning tree polytope of bounded-genus graphs
- Formulations and Reformulations in Integer Programming
- 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
- Lifts for Voronoi cells of lattices
- Two‐phase strategies for the bi‐objective minimum spanning tree problem
- An extended formulation for the 1‐wheel inequalities of the stable set polytope
- Computational comparisons of different formulations for the Stackelberg minimum spanning tree game
- An integer program for positive semidefinite zero forcing in graphs
- The role of rationality in integer-programming relaxations
- Dendrograms, minimum spanning trees and feature selection
- Linear-size formulations for connected planar graph partitioning and political districting
- A time-indexed LP-based approach for min-sum job-shop problems
- Circuits in extended formulations
- Multiplicative updates for symmetric-cone factorizations
- Constraint programming approaches for finding conserved metabolic and genomic patterns
- Exact approaches for the connected vertex cover problem
- The quadratic minimum spanning tree problem: lower bounds via extended formulations
- The ordered median tree location problem
- New strategy for anti-loop formulations
- Extended formulations for polygons
- Optimal cost augmentation and interdiction problem for the minimum spanning tree
- Characterization of facets of the hop constrained chain polytope via dynamic programming
- Uncapacitated flow-based extended formulations
- Intermediate integer programming representations using value disjunctions
This page was built for publication: Using separation algorithms to generate mixed integer model reformulations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1178714)
