On optimizing over lift-and-project closures
From MaRDI portal
Publication:2392660
DOI10.1007/S12532-012-0037-0zbMATH Open1275.90042arXiv1010.5412OpenAlexW2123691634MaRDI QIDQ2392660FDOQ2392660
Authors: Pierre Bonami 
Publication date: 2 August 2013
Published in: Mathematical Programming Computation (Search for Journal in Brave)
Abstract: The lift-and-project closure is the relaxation obtained by computing all lift-and-project cuts from the initial formulation of a mixed integer linear program or equivalently by computing all mixed integer Gomory cuts read from all tableau's corresponding to feasible and infeasible bases. In this paper, we present an algorithm for approximating the value of the lift-and-project closure. The originality of our method is that it is based on a very simple cut generation linear programming problem which is obtained from the original linear relaxation by simply modifying the bounds on the variables and constraints. This separation LP can also be seen as the dual of the cut generation LP used in disjunctive programming procedures with a particular normalization. We study some properties of this separation LP in particular relating it to the equivalence between lift-and-project cuts and Gomory cuts shown by Balas and Perregaard. Finally, we present some computational experiments and comparisons with recent related works.
Full work available at URL: https://arxiv.org/abs/1010.5412
Recommendations
- Lift-and-project cuts for convex mixed integer nonlinear programs
- Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants
- Lift-and-project for mixed 0-1 programming: recent progress
- Projected Chvátal-Gomory cuts for mixed integer linear programs
- A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Mixed integer programming (90C11)
Cites Work
- Solving Mixed Integer Programming Problems Using Automatic Reformulation
- Strengthening cuts for mixed integer programs
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- The Cutting-Plane Method for Solving Convex Programs
- Facets of the Knapsack Polytope From Minimal Covers
- Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
- Title not available (Why is that?)
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Title not available (Why is that?)
- Disjunctive programming: Properties of the convex hull of feasible points
- Reduce-and-Split cuts: improving the performance of mixed-integer Gomory cuts
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
- Optimizing over the first Chvátal closure
- Lift-and-project for mixed 0-1 programming: recent progress
- A relax-and-cut framework for Gomory mixed-integer cuts
- Split closure and intersection cuts
- A recursive procedure to generate all cuts for 0-1 mixed integer programs
- Optimizing over the split closure
- Edmonds polytopes and a hierarchy of combinatorial problems
- A heuristic to generate rank-1 GMI cuts
- Chvátal closures for mixed integer programming problems
- An in-out approach to disjunctive optimization
- Valid Linear Inequalities for Fixed Charge Problems
- Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation
- On the membership problem for the elementary closure of a polyhedron
- Projected Chvátal-Gomory cuts for mixed integer linear programs
- Title not available (Why is that?)
- A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming
- MIR closures of polyhedral sets
- Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants
- Practical strategies for generating rank-1 split cuts in mixed-integer linear programming
- On the separation of split cuts and related inequalities
- On the separation of disjunctive cuts
- Elementary closures for integer programs.
Cited In (20)
- Reformulating the disjunctive cut generating linear program
- Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants
- Lift-and-project cuts for convex mixed integer nonlinear programs
- Lift-and-project cuts for mixed integer convex programs
- Theoretical challenges towards cutting-plane selection
- Characterization of the split closure via geometric lifting
- Optimizing over the first Chvátal closure
- Title not available (Why is that?)
- Lattice reformulation cuts
- Cut generation through binarization
- Disjunctive cuts in mixed-integer conic optimization
- Surrogate-RLT cuts for zero-one integer programs
- Split cuts from sparse disjunctions
- Monoidal strengthening of simple \(\mathcal{V} \)-polyhedral disjunctive cuts
- Partial hyperplane activation for generalized intersection cuts
- Title not available (Why is that?)
- Computational experiments with cross and crooked cross cuts
- On the relative strength of different generalizations of split cuts
- Projected Chvátal-Gomory cuts for mixed integer linear programs
- Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design
Uses Software
This page was built for publication: On optimizing over lift-and-project closures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392660)
