A network approach for specially structured linear programs arising in 0–1 quadratic optimization

Reformulation techniques are commonly used to transform 0–1 quadratic problems into equivalent, mixed 0–1 linear programs. A classical strategy is to replace each quadratic term with a continuous variable and to enforce, for each such product, four linear inequalities that ensure the continuous variable equals the associated product. By employing a transformation of variables, we show how such inequalities give rise to a network structure, so that the continuous relaxations can be readily solved. This work unifies and extends related results for the vertex packing problem and relatives, and roof duality.