Comparisons and enhancement strategies for linearizing mixed 0–1 quadratic programs

We present a linearization strategy for mixed 0–1 quadratic programs that produces small formulations with tight relaxations. It combines constructs from a classical method of Glover and a more recent reformulation–linearization technique (RLT). By using binary identities to rewrite the objective, a variant of the first method results in a concise formulation with the level-1 RLT strength. This variant is achieved as a modified surrogate dual of a Langrangian subproblem to the RLT. Special structures can be exploited to obtain reductions in problem size, without forfeiting strength. Preliminary computational experience demonstrates the potential of the new representations.