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.