- | ||||
|
![]()
|
Dantzig Wolfe decomposition and objective function convexification for binary quadratic problems: the cardinality constrained quadratic knapsack case
Alberto Ceselli(alberto.ceselli 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 decomposition and Quadratic Convex Reformulation principles. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem, providing extensive experimental insights. We show that a few reformulations of our family yield to continuous relaxations that are strong in terms of dual bounds and computationally efficient to optimize. We report and analyze in depth a particular reformulation providing continuous relaxations whose solutions turn out to be integer optima in all our tests. We finally discuss on how to exploit these results in a generic binary quadratic programming context. Keywords: Binary Quadratic Programming, Objective Function Convexification, Dantzig-Wolfe Decomposition, Cardinality Constrained Quadratic Knapsack Category 1: Nonlinear Optimization (Quadratic Programming ) Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 3: Combinatorial Optimization Citation: Download: [PDF] Entry Submitted: 03/25/2017 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |