Lift-and-project for 0--1 programming via algebraic geometry
Luis Zuluaga (lzuluagaandrew.cmu.edu)
Abstract: Recently, tools from algebraic geometry have been successfully applied to develop solution schemes for new classes of optimization problems. A central idea in these constructions is to express a polynomial that is positive on a given domain in terms of polynomials of higher degree so that its positivity is readily revealed. This resembles the ``lifting'' phase of the lift-and-project procedures for 0--1 programming. We propose an enhancement to these solution schemes via a construction that is reminiscent of the ``projecting'' phase of the lift-and-project procedures. Our construction applies to domains that can be represented as the intersection of a set and an affine variety. To illustrate the power of our approach, we provide novel derivations of some of the lift-and-project procedures for 0--1 programming due to Balas, Ceria and Cornuejols; Sherali and Adams; Lovasz and Schrijver; and Lasserre. These derivations add new insight into this interesting subject, and suggest a number of variations and extensions.
Keywords: lift-and-project, algebraic geometry, 0--1 programming
Category 1: Integer Programming (0-1 Programming )
Category 2: Convex and Nonsmooth Optimization (Convex Optimization )
Category 3: Linear, Cone and Semidefinite Programming
Citation: GSIA Working Paper, Carnegie Mellon University, 2003.
Entry Submitted: 10/31/2003
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|