A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems

TLDR

The authors propose a reformulation that converts a linear zero‑one program into a polynomial program and then relinearizes it into an extended linear program. By varying the polynomial degree from one to the number of variables, the technique yields a hierarchy of increasingly tight relaxations that culminates in the convex hull, and it extends to polynomial problems, providing convex‑hull characterizations and tools for generating strong inequalities. The strength of the resulting relaxation increases with the polynomial degree, as illustrated by the provided examples.

Abstract

In this paper a reformulation technique is presented that takes a given linear zero-one programming problem, converts it into a zero-one polynomial programming problem, and then relinearizes it into an extended linear program. It is shown that the strength of the resulting reformulation depends on the degree of the terms used to produce the polynomial program at the intermediate step of this method. In fact, as this degree varies from one up to the number of variables in the problem, a hierarchy of sharper representations is obtained with the final relaxation representing the convex hull of feasible solutions. The reformulation technique readily extends to produce a similar hierarchy of linear relaxations for zero-one polynomial programming problems. A characterization of the convex hull in the original variable space is also available through a projection process. The structure of this convex hull characterization (or its other relaxations) can be exploited to generate strong or facetial valid inequalities through appropriate surrogates in a computational framework. The surrogation process can also be used to study various classes of facets for different combinatorial optimization problems. Some examples are given to illustrate this point.