Using separation algorithms to generate mixed integer model reformulations
From MaRDI portal
Publication:1178714
DOI10.1016/0167-6377(91)90028-NzbMath0747.90071MaRDI QIDQ1178714
Publication date: 26 June 1992
Published in: Operations Research Letters (Search for Journal in Brave)
cutting plane; linear relaxation; auxiliary variables; graph optimization; separation algorithm; model reformulation; traversal matroid
90C35: Programming involving graphs or networks
90C11: Mixed integer programming
90-08: Computational methods for problems pertaining to operations research and mathematical programming
Related Items
Learning in Combinatorial Optimization: What and How to Explore, The Optimal Design of Low-Latency Virtual Backbones, Deriving compact extended formulations via LP-based separation techniques, Deriving compact extended formulations via LP-based separation techniques, 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, Mixed integer linear programming formulations for probabilistic constraints, Smaller extended formulations for the spanning tree polytope of bounded-genus graphs, A time-indexed LP-based approach for min-sum job-shop problems, Extended formulations for polygons, Characterization of facets of the hop constrained chain polytope via dynamic programming, Extended formulations, nonnegative factorizations, and randomized communication protocols, Uncapacitated flow-based extended formulations, Lower bounds on the sizes of integer programs without additional variables, Simple extensions of polytopes, Intermediate integer programming representations using value disjunctions, 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, 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, Mixed Integer Linear Programming Formulation Techniques, On Vertices and Facets of Combinatorial 2-Level Polytopes, 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
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On cuts and matchings in planar graphs
- Valid inequalities and separation for uncapacitated fixed charge networks
- Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
- Gainfree Leontief substitution flow problems
- Operations that preserve total dual integrality
- The perfectly matchable subgraph polytope of a bipartite graph
- Modelling with integer variables
- A dual ascent approach for steiner tree problems on a directed graph
- Uncapacitated lot-sizing: The convex hull of solutions
- Uncapacitated Lot-Sizing Problems with Start-Up Costs
- Trees and Cuts
- Minimum cuts, modular functions, and matroid polyhedra
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- Selected Applications of Minimum Cuts in Networks
- Reformulation of the Multiperiod MILP Model for Capacity Expansion of Chemical Processes
- On the cut polytope
- A Selection Problem of Shared Fixed Costs and Network Flows
