Optimization Online


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

Alberto Ceselli(alberto.ceselli***at***unimi.it)
Lucas Létocart(lucas.letocart***at***lipn.univ-paris13.fr)
Emiliano Traversi(emiliano.traversi***at***lipn.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


Download: [PDF]

Entry Submitted: 03/25/2017
Entry Accepted: 03/25/2017
Entry Last Modified: 03/25/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society