We propose two exact approaches for non-convex quadratic integer minimization subject to linear constraints where lower bounds are computed by considering ellipsoidal relaxations of the feasible set. In the first approach, we intersect the ellipsoids with the feasible linear subspace. In the second approach we penalize exactly the linear constraints. We investigate the connection between both approaches theoretically. Experimental results show that the penalty approach significantly outperforms CPLEX on problems with small or medium size variable domains. © 2015 Elsevier B.V. All rights reserved.
A fast branch-and-bound algorithm for non-convex quadratic integer optimization subject to linear constraints using ellipsoidal relaxations / Buchheim, Christoph; DE SANTIS, Marianna; Palagi, Laura. - In: OPERATIONS RESEARCH LETTERS. - ISSN 0167-6377. - STAMPA. - 43:4(2015), pp. 384-388. [10.1016/j.orl.2015.05.001]
A fast branch-and-bound algorithm for non-convex quadratic integer optimization subject to linear constraints using ellipsoidal relaxations
DE SANTIS, MARIANNA
;PALAGI, Laura
2015
Abstract
We propose two exact approaches for non-convex quadratic integer minimization subject to linear constraints where lower bounds are computed by considering ellipsoidal relaxations of the feasible set. In the first approach, we intersect the ellipsoids with the feasible linear subspace. In the second approach we penalize exactly the linear constraints. We investigate the connection between both approaches theoretically. Experimental results show that the penalty approach significantly outperforms CPLEX on problems with small or medium size variable domains. © 2015 Elsevier B.V. All rights reserved.File | Dimensione | Formato | |
---|---|---|---|
Buchheim_A-fast-branch-and-bound_Preprint_2015.pdf
accesso aperto
Tipologia:
Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza:
Creative commons
Dimensione
139.75 kB
Formato
Adobe PDF
|
139.75 kB | Adobe PDF | |
Buchheim_A-fast-branch-and-bound_2015.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
388.44 kB
Formato
Adobe PDF
|
388.44 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.