Using separation algorithms to generate mixed integer model reformulations

DOI10.1016/0167-6377(91)90028-NzbMath0747.90071OpenAlexW2161226285MaRDI QIDQ1178714

Publication date: 26 June 1992

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(91)90028-n

zbMATH Keywords

cutting plane linear relaxation auxiliary variables graph optimization separation algorithm model reformulation traversal matroid

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (72)

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 ⋮ Sparktope: linear programs from algorithms ⋮ Extended formulations for sparsity matroids ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ New formulations for the elementary shortest-path problem visiting a given set of nodes ⋮ Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations ⋮ Extended formulations for independence polytopes of regular matroids ⋮ Intersection Disjunctions for Reverse Convex Sets ⋮ Regular Matroids Have Polynomial Extension Complexity ⋮ Strong formulations for mixed integer programming: A survey ⋮ On the extension complexity of scheduling polytopes ⋮ Long range planning in the process industries: A projection approach ⋮ Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem ⋮ A result on projection for the vehicle routing problem ⋮ 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 ⋮ Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods ⋮ On the combinatorial lower bound for the extension complexity of the spanning tree polytope ⋮ Optimal design of switched Ethernet networks implementing the multiple spanning tree protocol ⋮ 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 ⋮ Lower bounds on the sizes of integer programs without additional variables ⋮ Simple extensions of polytopes ⋮ Node packings on cocomparability graphs ⋮ Connected power domination 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 ⋮ Some \(0/1\) polytopes need exponential size extended formulations ⋮ Fooling sets and the spanning tree polytope ⋮ Certifiably optimal sparse inverse covariance estimation ⋮ Mixed integer linear programming formulations for probabilistic constraints ⋮ A time-indexed LP-based approach for min-sum job-shop problems ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Parsimonious formulations for low-diameter clusters ⋮ Learning in Combinatorial Optimization: What and How to Explore ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ The \(k\)-Track assignment problem on partial orders ⋮ Intermediate integer programming representations using value disjunctions ⋮ Valid inequalities for the single arc design problem with set-ups ⋮ Ordered weighted average optimization in multiobjective spanning tree problem ⋮ The prize-collecting generalized minimum spanning tree problem ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Smaller extended formulations for the spanning tree polytope of bounded-genus graphs ⋮ Extended formulations for polygons ⋮ Subgraph polytopes and independence polytopes of count matroids ⋮ 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 ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ Extended formulations for radial cones ⋮ Mixed Integer Linear Programming Formulation Techniques ⋮ Characterization of facets of the hop constrained chain polytope via dynamic programming ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ Extended formulations, nonnegative factorizations, and randomized communication protocols ⋮ Uncapacitated flow-based extended formulations ⋮ On the linear extension complexity of stable set polytopes for perfect graphs ⋮ The splitting of variables and constraints in the formulation of integer programming models ⋮ On Vertices and Facets of Combinatorial 2-Level Polytopes ⋮ An effective compact formulation of the max cut problem on sparse graphs ⋮ Lower bounds on matrix factorization ranks via noncommutative polynomial optimization ⋮ Extended formulations of lower-truncated transversal polymatroids ⋮ Electrical flows over spanning trees ⋮ Polyhedral description of the integer single node flow set with constant bounds ⋮ A branch-and-cut algorithm for multiple sequence alignment ⋮ A generalization of extension complexity that captures P ⋮ Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems ⋮ Compact vs. exponential-size LP relaxations

Uses Software

LINDO

Cites Work

This page was built for publication: Using separation algorithms to generate mixed integer model reformulations