Recent Advanced in Lift-and-Project
Abstract
In recent years the lift-and-project approach has been used successfully within a branch-and-cut framework to solve large. difficult pure and mixed 0-1 programs that have resisted solution efforts by pure branch and bound codes. The approach uses a linear description in a higher dimensional space of the convex hull of the disjunctive set created by imposing one or several 0-1 conditions. By solving a linear program derived from this higher dimensional representation - the cut generating linear program (CGLP) - the standard lift-and-project procedure obtains a deepest cut in a well defined sense. we propose a modification of CGLP that allows us to generate not just one deepest cut. but a class of cuts with desirable properties each at the cost of one extra pivot in the optimal tableau of the modified CGLP.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1997
- Accession Number
- ADA351870
Entities
People
- Egon Balas
Organizations
- Carnegie Mellon University