UNCONSTRAINED 0-1 OPTIMIZATION AND LAGRANGEAN RELAXATION

We consider the problem of maximizing a general pseudo-Boolean function. We formulate the problem as a constrained 0-1 polynomial program and show how to compute an upper bound on the maximum objective function value through the construction of a Lagrangean dual. It turns out that this Lagrangean dual yields an optimal objective value equal to the roof dual value for 0-1 polynomial programming problems. In fact, the posed Lagrangean dual motivates a linear programming problem whose dual is strongly related to the set of upper bounding planes known as roofs. Using this linear programming problem and the Kuhn-Tucker complementary slackness conditions, we show that for a given problem the task of determining whether a roof duality gap exists is equivalent to the checking of the consistency of a 0-1 quadratic posiform. This result is significant since the consistency of a 0-1 quadratic posiform can be checked in time linear in the number of terms. © 1990.