Optimizing over the split closure

DOI10.1007/S10107-006-0049-5zbMath1135.90030OpenAlexW2083625505MaRDI 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 cutsalgorithmic framework

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (51)

How to select a small set of diverse solutions to mixed integer programming problems ⋮ Disjunctive Cuts for Nonconvex MINLP ⋮ MIPping closures: An instant survey ⋮ MIP reformulations of the probabilistic set covering problem ⋮ MIR closures of polyhedral sets ⋮ Characterization of the split closure via geometric lifting ⋮ Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations ⋮ Surrogate-RLT cuts for zero-one integer programs ⋮ On optimizing over lift-and-project closures ⋮ Local cuts for mixed-integer programming ⋮ Multirow Intersection Cuts Based on the Infinity Norm ⋮ Optimizing over the first Chvátal closure ⋮ Partial hyperplane activation for generalized intersection cuts ⋮ Computational Experiments with Cross and Crooked Cross Cuts ⋮ On the enumerative nature of Gomory's dual cutting plane method ⋮ Practical strategies for generating rank-1 split cuts in mixed-integer linear programming ⋮ On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube ⋮ Bilevel programming and the separation problem ⋮ A heuristic to generate rank-1 GMI cuts ⋮ On the relative strength of split, triangle and quadrilateral cuts ⋮ Cut generation through binarization ⋮ Optimal Cutting Planes from the Group Relaxations ⋮ Split cuts from sparse disjunctions ⋮ Outer-product-free sets for polynomial optimization and oracle-based cuts ⋮ Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems ⋮ Lift-and-project cuts for convex mixed integer nonlinear programs ⋮ 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 ⋮ Coordinated cutting plane generation via multi-objective separation ⋮ 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 ⋮ Using symmetry to optimize over the Sherali-Adams relaxation ⋮ Relaxations of mixed integer sets from lattice-free polyhedra ⋮ A Probabilistic Analysis of the Strength of the Split and Triangle Closures ⋮ Lower Bounds on the Lattice-Free Rank for Packing and Covering Integer Programs ⋮ On the relative strength of different generalizations of split cuts ⋮ Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning ⋮ Lattice Reformulation Cuts ⋮ Parametric mixed-integer 0-1 linear programming: The general case for a single parameter ⋮ Erratum to: MIR closures of polyhedral sets ⋮ A relax-and-cut framework for Gomory mixed-integer cuts ⋮ Relaxations of mixed integer sets from lattice-free polyhedra ⋮ On the exact separation of mixed integer knapsack cuts ⋮ On the separation of disjunctive cuts ⋮ Valid inequalities for mixed integer linear programs ⋮ A lexicographic pricer for the fractional bin packing problem ⋮ Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants ⋮ Virtual private network design over the first Chvátal closure ⋮ Combinatorial Optimization: The Interplay of Graph Theory, Linear and Integer Programming Illustrated on Network Flow

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

This page was built for publication: Optimizing over the split closure