Constrained 0-1 Quadratic Programming: Basic Approaches and Extensions

We describe the simplest technique to tackle 0-1 Quadratic Programs with linear constraints among those that turn out to be successful in practice. This method is due to and familiar to the Quadratic Assignment experts, even if it took some time to realize that most approaches to the problem could be interpreted in these terms, whereas it does not appear to be widely known outside this community. Since the technique is completely general and is by far the most successful one in several other cases, such as Quadratic Knapsack, we illustrate it in its full generality, pointing out its relationship to Lagrangian and linear programming relaxations and discussing further extensions. We believe that this method should be in the background of every practitioner in Combinatorial Optimization.