Optimization Online


Lift-and-project for 0--1 programming via algebraic geometry

Luis Zuluaga (lzuluaga***at***andrew.cmu.edu)
Juan Vera (jvera***at***andrew.cmu.edu)
Javier Pena (jfp***at***andrew.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.

Download: [Postscript][PDF]

Entry Submitted: 10/31/2003
Entry Accepted: 10/31/2003
Entry Last Modified: 12/04/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society