Solving 0–1 quadratic programs by reformulation techniques

A1 Originalartikel i en vetenskaplig tidskrift (referentgranskad)

Interna författare/redaktörer

Publikationens författare: Ray Pörn, Otto Nissfolk, Anders Skjäl, Tapio Westerlund
Förläggare: American Chemical Society
Publiceringsår: 2017
Tidskrift: Industrial & Engineering Chemistry Research
Tidskriftsakronym: Ind. Eng. Chem. Res.
Volym: 56
Nummer: 45
Artikelns första sida, sidnummer: 13444
Artikelns sista sida, sidnummer: 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.

Senast uppdaterad 2020-09-08 vid 07:55