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.
Citation
GSIA Working Paper, Carnegie Mellon University, 2003.
Article
View Lift-and-project for 0--1 programming via algebraic geometry