Solving 0–1 quadratic programs by reformulation techniques

A1 Journal article (refereed)

Internal Authors/Editors

Publication Details

List of Authors: Ray Pörn, Otto Nissfolk, Anders Skjäl, Tapio Westerlund
Publisher: American Chemical Society
Publication year: 2017
Journal: Industrial & Engineering Chemistry Research
Journal acronym: Ind. Eng. Chem. Res.
Volume number: 56
Issue number: 45
Start page: 13444
End page: 13453
eISSN: 1520-5045


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.

Last updated on 2019-20-10 at 03:31