Technical Note—Generalized Covering Relaxation for 0-1 Programs

We construct in this paper a general purpose cutting-plane algorithm for solving the 0-1 polynomial programming problem of finding a 0-1 n vector x = (x_j) that maximizes c^Tx subject to f(x) ≤ b where f(x) = (f_i(x)) is an m vector of polynomials. The algorithm consists of solving a nested sequence of linear generalized covering problems, i.e., covering problems involving both the original variables x and their complements x̄ = 1 − x. Each problem in the sequence is a relaxation of the original 0-1 polynomial program, and is obtained by adding to its predecessor a small number of generalized covering constraints that are violated by the optimal solution for the preceding generalized covering problem. Over 95% of more than 800 randomly generated problems with up to 70 variables and 50 constraints and mostly up to 5 terms in each constraint were solved by our method in less than 90 seconds of CPU time on an AMDAHL 470 V-6 computer.