Optimizing over the split closure

DOI10.1007/s10107-006-0049-5zbMath1135.90030MaRDI QIDQ2476990

Egon Balas, Anureet Saxena

Publication date: 12 March 2008

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0049-5

zbMATH Keywords

split cuts; algorithmic framework

Mathematics Subject Classification ID

90C11: Mixed integer programming

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

Related Items

Relaxations of mixed integer sets from lattice-free polyhedra, A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts, A computational study of the cutting plane tree algorithm for general mixed-integer linear programs, On the exact separation of mixed integer knapsack cuts, On the separation of disjunctive cuts, On the enumerative nature of Gomory's dual cutting plane method, A heuristic to generate rank-1 GMI cuts, On the relative strength of split, triangle and quadrilateral cuts, Lexicography and degeneracy: Can a pure cutting plane algorithm work?, A note on the split rank of intersection cuts, Improved strategies for branching on general disjunctions, Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations, How to select a small set of diverse solutions to mixed integer programming problems, MIP reformulations of the probabilistic set covering problem, MIR closures of polyhedral sets, Optimizing over the first Chvátal closure, Parametric mixed-integer 0-1 linear programming: The general case for a single parameter, Erratum to: MIR closures of polyhedral sets, Valid inequalities for mixed integer linear programs, Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants, A relax-and-cut framework for Gomory mixed-integer cuts, MIPping closures: An instant survey, Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations, Disjunctive Cuts for Nonconvex MINLP, A Probabilistic Analysis of the Strength of the Split and Triangle Closures

Uses Software

• MIPLIB
• CPLEX
• OR-Library
• COIN-OR

Cites Work

• Lift-and-project for mixed 0-1 programming: recent progress
• Chvátal closures for mixed integer programming problems
• Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation
• An exact algorithm for the capacitated facility location problems with single sourcing
• A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming
• On the separation of split cuts and related inequalities
• On splittable and unsplittable flow capacitated network design arc-set polyhedra.
• Split closure and intersection cuts
• A study of the lot-sizing polytope
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Projected Chvátal-Gomory cuts for mixed integer linear programs
• The vertex separator problem: algorithms and computations
• The vertex separator problem: a polyhedral investigation
• A Multi-Exchange Heuristic for the Single-Source Capacitated Facility Location Problem
• Optimizing over the First Chvàtal Closure
• The Homotopy Principle and Algorithms for Linear Programming
• Disjunctive Programming
• Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
• Elementary closures for integer programs.
• Flow pack facets of the single node fixed-charge flow polytope