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

Luis Zuluaga (lzuluagaandrew.cmu.edu)
Juan Vera (jveraandrew.cmu.edu)
Javier Pena (jfpandrew.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