The purpose of this paper is to provide strong reformulations for binary quadratic problems. We propose a first methodological analysis on a family of reformulations combining Dantzig-Wolfe and Quadratic Convex optimization principles. We show that a few reformulations of our family yield continuous relaxations that are strong in terms of dual bounds and computationally efficient to optimize. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem, providing extensive experimental insights. We report and analyze in depth a particular reformulation providing continuous relaxations whose solutions turn out to be integer optima in all our tests.
Dantzig-Wolfe reformulations for binary quadratic problems / A. Ceselli, L. L('e)tocart, E. Traversi. - In: MATHEMATICAL PROGRAMMING COMPUTATION. - ISSN 1867-2949. - 14:1(2022 Mar), pp. 85-120. [10.1007/s12532-021-00206-w]
Dantzig-Wolfe reformulations for binary quadratic problems
A. Ceselli
Primo
;
2022
Abstract
The purpose of this paper is to provide strong reformulations for binary quadratic problems. We propose a first methodological analysis on a family of reformulations combining Dantzig-Wolfe and Quadratic Convex optimization principles. We show that a few reformulations of our family yield continuous relaxations that are strong in terms of dual bounds and computationally efficient to optimize. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem, providing extensive experimental insights. We report and analyze in depth a particular reformulation providing continuous relaxations whose solutions turn out to be integer optima in all our tests.File | Dimensione | Formato | |
---|---|---|---|
QDWD_revision2.pdf
accesso aperto
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
478.65 kB
Formato
Adobe PDF
|
478.65 kB | Adobe PDF | Visualizza/Apri |
s12532-021-00206-w.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
523.56 kB
Formato
Adobe PDF
|
523.56 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.