Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation

DOI10.1016/j.disopt.2005.08.006zbMath1172.90450OpenAlexW2066961446MaRDI QIDQ1019294

Pierre Bonami, Michel Minoux

Publication date: 2 June 2009

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2005.08.006

zbMATH Keywords

Mixed integer programmingLift-and-projectCutting-planesrank-1 closures

Mathematics Subject Classification ID

Mixed integer programming (90C11)

Related Items

MIR closures of polyhedral sets, Surrogate-RLT cuts for zero-one integer programs, Theoretical challenges towards cutting-plane selection, On optimizing over lift-and-project closures, DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips, A heuristic to generate rank-1 GMI cuts, Lift-and-project cuts for convex mixed integer nonlinear programs, A computational study of the cutting plane tree algorithm for general mixed-integer linear programs, Reflections on generating (disjunctive) cuts, Using symmetry to optimize over the Sherali-Adams relaxation, Lift-and-Project Cuts for Mixed Integer Convex Programs, A new lift-and-project operator, Optimizing over the split closure, Projected Chvátal-Gomory cuts for mixed integer linear programs, RLT insights into lift-and-project closures, A relax-and-cut framework for Gomory mixed-integer cuts, Valid inequalities for mixed integer linear programs, Cutting planes for RLT relaxations of mixed 0-1 polynomial programs

Uses Software

• MIPLIB
• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lift-and-project for mixed 0-1 programming: recent progress
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Partitioning procedures for solving mixed-variables programming problems
• Strengthening cuts for mixed integer programs
• A genetic algorithm for the multidimensional knapsack problem
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• Disjunctive programming: Properties of the convex hull of feasible points
• The Steiner tree polytope and related polyhedra
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• A polyhedral approach to multicommodity survivable network design
• A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming
• Discrete cost multicommodity network optimization problems and exact solution methods
• Computational experience with a difficult mixed-integer multicommodity flow problem
• 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
• Exact MAX-2SAT solution via lift-and-project closure
• Gomory cuts revisited
• Reduce-and-Split Cuts: Improving the Performance of Mixed-Integer Gomory Cuts
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Aggregation and Mixed Integer Rounding to Solve MIPs
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Facets for Polyhedra Arising in the Design of Communication Networks with Low-Connectivity Constraints
• Solving the Steiner Tree Problem on a Graph Using Branch and Cut
• Disjunctive Programming
• Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
• Elementary closures for integer programs.