Elementary closures for integer programs.

DOI10.1016/S0167-6377(00)00067-5zbMath1108.90326OpenAlexW1975254220MaRDI QIDQ5937498

Cornuéjols, Gérard, Yanjun Li

Publication date: 12 July 2001

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

Full work available at URL: https://doi.org/10.1016/s0167-6377(00)00067-5

zbMATH Keywords

Integer programmingCutting planeElementary closure

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

MIR closures of polyhedral sets, Two row mixed-integer cuts via lifting, Theoretical challenges towards cutting-plane selection, On optimizing over lift-and-project closures, Intersection Disjunctions for Reverse Convex Sets, DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips, On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube, Monoidal strengthening of simple \(\mathcal{V} \)-polyhedral disjunctive cuts, A heuristic to generate rank-1 GMI cuts, Generating valid linear inequalities for nonlinear programs via sums of squares, Lexicography and degeneracy: Can a pure cutting plane algorithm work?, A note on the split rank of intersection cuts, The mixing-MIR set with divisible capacities, Monoidal cut strengthening and generalized mixed-integer rounding for disjunctions and complementarity constraints, Exact MAX-2SAT solution via lift-and-project closure, A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO), On the relative strength of different generalizations of split cuts, Design and verify: a new scheme for generating cutting-planes, Optimizing over the split closure, RLT insights into lift-and-project closures, A relax-and-cut framework for Gomory mixed-integer cuts, Split closure and intersection cuts, Unnamed Item, Valid inequalities for mixed integer linear programs, The Cutting Plane Method is Polynomial for Perfect Matchings, On the polyhedral lift-and-project methods and the fractional stable set polytope, Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation, Depth-optimized convexity cuts, Strengthening Chvátal-Gomory cuts and Gomory fractional cuts

Cites Work

• Cutting planes in integer and mixed integer programming
• Chvátal closures for mixed integer programming problems
• On the membership problem for the elementary closure of a polyhedron
• Strengthening cuts for mixed integer programs
• A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming
• A recursive procedure to generate all cuts for 0-1 mixed integer programs
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Edmonds polytopes and a hierarchy of combinatorial problems
• On the Matrix-Cut Rank of Polyhedra
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Outline of an algorithm for integer solutions to linear programs
• On Cutting Planes
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Two Rules for Deducing Valid Inequalities for 0-1 Problems
• Disjunctive Programming
• Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item