A Lagrangian dual and surrogate method for multi-dimensional quadratic knapsack problems

Pages: 47 - 60, Volume 5, Issue 1, February 2009

doi:10.3934/jimo.2009.5.47       Abstract        Full Text (191.8K)       Related Articles

Xiaoling Sun - School of Management, Fudan University, Shanghai 200433, China (email)
Xiaojin Zheng - Department of Mathematics, Shanghai University, Shanghai 200444, China (email)
Juan Sun - Department of Mathematics, Shanghai University, Shanghai 200444, China (email)

Abstract: Quadratic 0-1 knapsack problems have a variety of applications in various areas such as flexible manufacturing systems, location of transportation facilities and telecommunications. In this paper we present a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems. Outer approximation and bundle method are used to compute the Lagrangian bound where the Lagrangian relaxation is solved by the maximum flow algorithm. We also present a surrogate constraint heuristic for finding feasible solutions. Preliminary computational results for small to medium size test problems are reported.

Keywords:  Multi-dimensional quadratic 0-1 knapsack problem, branch-and-bound method, outer approximation, bundle method.
Mathematics Subject Classification:  Primary: 90C10, 90C20; Secondary: 90C11.

Received: April 2008;      Revised: October 2008;      Published: December 2008.