Dantzig Wolfe decomposition and objective function convexification for binary quadratic problems: the cardinality constrained quadratic knapsack case

Alberto Ceselli(alberto.ceselliunimi.it)
Lucas Létocart(lucas.letocartlipn.univ-paris13.fr)
Emiliano Traversi(emiliano.traversilipn.univ-paris13.fr)

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
Entry Accepted: 03/25/2017
Entry Last Modified: 03/25/2017

Modify/Update this entry