A lift-and-project cutting plane algorithm for mixed 0-1 programming problems

A lift-and-project cutting plane algorithm for mixed 0-1 programming problems

0.00 Avg rating0 Votes
Article ID: iaor19941905
Country: Netherlands
Volume: 58
Issue: 3
Start Page Number: 295
End Page Number: 324
Publication Date: Feb 1993
Journal: Mathematical Programming (Series A)
Authors: , ,
Abstract:

The authors propose a cutting plane algorithm for mixed 0-1 programs based on a family of polyhedra which strengthen the usual LP relaxation. They 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 strengthening step suggested by Balas and Jeroslow is then applied. The authors report the present computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cone relaxations of Lovász and Schrijver and the hierarchy of relaxations of Sherali and Adams.

Reviews

Required fields are marked *. Your email address will not be published.