A Lift-and-Project Cutting Plane Algorithm for Mixed 0-1 Programs

Abstract

We propose a cutting plane algorithm for programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through the solution of a linear program that has, about twice the size of the usual LP relaxation. A lifting step is used to reduce the size of the LP's needed to generate the cuts. An additional strengthened step suggested by Balas and Jeroslow is then applied. We report our computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cut relaxations of Lovasz and Schrijver and the hierarchy of relaxations of Sherali and Adams.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1991
Accession Number
ADA249360

Entities

People

  • Egon Balas
  • Gérard Cornuéjols
  • Sebastian Ceria

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Computer Programming
  • Convex Sets
  • Equations
  • Evolutionary Algorithms
  • Inequalities
  • Integer Programming
  • Linear Programming
  • Linear Systems
  • Mathematical Programming
  • Nonlinear Systems
  • Numbers
  • Operations Research
  • Optimization
  • Theorems
  • Trees (Data Structures)

Readers

  • Operations Research