A relax-and-cut framework for Gomory mixed-integer cuts

DOI10.1007/s12532-011-0024-xzbMath1257.90057OpenAlexW1990925151MaRDI QIDQ1762453

Matteo Fischetti, Domenico Salvagnin

Publication date: 27 November 2012

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-011-0024-x

zbMATH Keywords

Lagrangian relaxationrelax-and-cutGomory cuts

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Extreme-point and pivoting methods (90C49)

Related Items

Characterization of the split closure via geometric lifting, Theoretical challenges towards cutting-plane selection, On optimizing over lift-and-project closures, Computational Experiments with Cross and Crooked Cross Cuts, Split cuts from sparse disjunctions, On the relative strength of different generalizations of split cuts, Lattice Reformulation Cuts, Strong IP formulations need large coefficients, Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization, The strength of multi-row models

Uses Software

• SCIP
• MIPLIB
• COIN-OR
• FEASPUMP
• MIPLIB2003
• Cgllandp

Cites Work

• Unnamed Item
• Revival of the Gomory cuts in the 1990's
• A heuristic to generate rank-1 GMI cuts
• Lexicography and degeneracy: Can a pure cutting plane algorithm work?
• SCIP: solving constraint integer programs
• Non delayed relax-and-cut algorithms
• MIR closures of polyhedral sets
• Optimizing over the first Chvátal closure
• Valid inequalities for mixed integer linear programs
• Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation
• Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants
• Feasibility pump 2.0
• Strengthening cuts for mixed integer programs
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming
• On the capacitated vehicle routing problem
• Information-based branching schemes for binary linear mixed integer problems
• Optimizing over the split closure
• Gomory cuts revisited
• Embedding {0, ½}-Cuts in a Branch-and-Cut Framework: A Computational Study
• Integer Programming and Pricing
• A Heuristic Method for the Set Covering Problem
• Elementary closures for integer programs.