Solving 0–1 quadratic programs by reformulation techniques

Ray Pörn, Otto Nissfolk, Anders Skjäl, Tapio Westerlund

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)


We derive and study a reformulation technique for general 0–1 quadratic programs (QP) that uses diagonal as well as nondiagonal perturbation of the objective function. The technique is an extension of the Quadratic Convex Reformulation (QCR) method developed by Billionnet and co-workers, adding nondiagonal perturbations, whereas QCR is in a sense diagonal. In this work a set of redundant reformulation-linearization technique (RLT) inequalities are included in the problem. The redundant inequalities are used to induce nondiagonal perturbations of the objective function that improve the bounding characteristics of the continuous relaxation. The optimal convexification is obtained from the solution of a semidefinite program. We apply the nondiagonal QCR (NDQCR) technique to four different types of problems and compare the bounding properties and solution times with the original QCR method. The proposed method outperforms the original QCR method on all four types of test problems.

Original languageUndefined/Unknown
Pages (from-to)13444–13453
JournalIndustrial & Engineering Chemistry Research
Issue number45
Publication statusPublished - 2017
MoE publication typeA1 Journal article-refereed

Cite this