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

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.