Solving 0–1 quadratic programs by reformulation techniques

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

Tutkimustuotos: LehtiartikkeliArtikkeliTieteellinenvertaisarvioitu

2 Sitaatiot (Scopus)

Abstrakti

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.

AlkuperäiskieliEi tiedossa
Sivut13444–13453
JulkaisuIndustrial & Engineering Chemistry Research
Vuosikerta56
Numero45
DOI - pysyväislinkit
TilaJulkaistu - 2017
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Viittausmuodot