.png){kind=icon}
.png){kind=icon}
Return
Dantzig-Wolfe reformulations for binary quadratic problems
.png){kind=icon}
OA
AI
DOI：10.1007/s12532-021-00206-w.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Binary quadratic programming
Decomposition methods
Quadratic convex reformulation
Column generation
Journal
IF:
3.6
Papers:
194
Citations:
1.9K