On optimizing over lift-and-project closures
From MaRDI portal
Publication:2392660
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.
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
Cites work
- scientific article; zbMATH DE number 3156817 (Why is no real title available?)
- scientific article; zbMATH DE number 2196290 (Why is no real title available?)
- scientific article; zbMATH DE number 3373541 (Why is no real title available?)
- A heuristic to generate rank-1 GMI cuts
- A lift-and-project cutting plane algorithm for mixed 0-1 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 relax-and-cut framework for Gomory mixed-integer cuts
- An in-out approach to disjunctive optimization
- Chvátal closures for mixed integer programming problems
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
- Disjunctive programming: Properties of the convex hull of feasible points
- Edmonds polytopes and a hierarchy of combinatorial problems
- Elementary closures for integer programs.
- Facets of the Knapsack Polytope From Minimal Covers
- Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Lift-and-project for mixed 0-1 programming: recent progress
- MIR closures of polyhedral sets
- Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
- On the membership problem for the elementary closure of a polyhedron
- On the separation of disjunctive cuts
- On the separation of split cuts and related inequalities
- Optimizing over the first Chvátal closure
- Optimizing over the split closure
- Practical strategies for generating rank-1 split cuts in mixed-integer linear programming
- Projected Chvátal-Gomory cuts for mixed integer linear programs
- Reduce-and-Split cuts: improving the performance of mixed-integer Gomory cuts
- Solving Mixed Integer Programming Problems Using Automatic Reformulation
- Split closure and intersection cuts
- Strengthening cuts for mixed integer programs
- The Cutting-Plane Method for Solving Convex Programs
- Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation
- Valid Linear Inequalities for Fixed Charge Problems
Cited in
(20)- Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design
- 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
- scientific article; zbMATH DE number 2084778 (Why is no real title available?)
- Cut generation through binarization
- Surrogate-RLT cuts for zero-one integer programs
- Lattice reformulation cuts
- Disjunctive cuts in mixed-integer conic optimization
- Split cuts from sparse disjunctions
- Monoidal strengthening of simple \(\mathcal{V} \)-polyhedral disjunctive cuts
- Partial hyperplane activation for generalized intersection cuts
- scientific article; zbMATH DE number 6707767 (Why is no real title available?)
- 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
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)
