Projection, Lifting and Extended Formulation in Integer and Combinatorial Optimization

Egon Balas

Annals of Operations Research, 2005, vol. 140, issue 1, 125-161

Abstract: This is an overview of the significance and main uses of projection, lifting and extended formulation in integer and combinatorial optimization. Its first two sections deal with those basic properties of projection that make it such an effective and useful bridge between problem formulations in different spaces, i.e. different sets of variables. They discuss topics like projection and restriction, the integrality-preserving property of projection, the dimension of projected polyhedra, conditions for facets of a polyhedron to project into facets of its projections, and so on. The next two sections describe the use of projection for comparing the strength of different formulations of the same problem, and for proving the integrality of polyhedra by using extended formulations or lifting. Section 5 deals with disjunctive programming, or optimization over unions of polyhedra, whose most important incarnation are mixed 0-1 programs and their partial relaxations. It discusses the compact representation of the convex hull of a union of polyhedra through extended formulation, the connection between the projection of the latter and the polar of the convex hull, as well as the sequential convexification of facial disjunctive programs, among them mixed 0-1 programs, with the related concept of disjunctive rank. Section 6 reviews lift-and-project cuts, the construction of cut generating linear programs, and techniques for lifting and for strengthening disjunctive cuts. Section 7 discusses the recently discovered possibility of solving the higher dimensional cut generating linear program without explicitly constructing it, by a sequence of properly chosen pivots in the simplex tableau of the linear programming relaxation. Finally, section 8 deals with different ways of combining cuts with branch and bound, and briefly discusses computational experience with lift-and-project cuts. Copyright Springer Science + Business Media, Inc. 2005

Keywords: disjunctive programming; sequential convexification; 0-1 programming; lift-and-project (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-005-3969-1 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:140:y:2005:i:1:p:125-161:10.1007/s10479-005-3969-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-005-3969-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().