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

Previous Article
An empirical study on discrete optimization models for portfolio selection
JIMO Home
This Issue
Next Article
Deterministic modeling of whole-body sheep metabolism

January 2009, 5(1): 47-60. doi: 10.3934/jimo.2009.5.47

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

Xiaoling Sun ^1, , Xiaojin Zheng ^2, and Juan Sun ^2,

1.	School of Management, Fudan University, Shanghai 200433
2.	Department of Mathematics, Shanghai University, Shanghai 200444, China, China

Received April 2008 Revised October 2008 Published December 2008

Abstract
Related Papers

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: branch-and-bound method, bundle method., outer approximation, Multi-dimensional quadratic 0-1 knapsack problem.

Mathematics Subject Classification: Primary: 90C10, 90C20; Secondary: 90C1.

Citation: Xiaoling Sun, Xiaojin Zheng, Juan Sun. A Lagrangian dual and surrogate method for multi-dimensional quadratic knapsack problems. Journal of Industrial & Management Optimization, 2009, 5 (1) : 47-60. doi: 10.3934/jimo.2009.5.47

[1]	Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial & Management Optimization, 2013, 9 (3) : 531-547. doi: 10.3934/jimo.2013.9.531
[2]	Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019044
[3]	Xiaoling Sun, Hongbo Sheng, Duan Li. An exact algorithm for 0-1 polynomial knapsack problems. Journal of Industrial & Management Optimization, 2007, 3 (2) : 223-232. doi: 10.3934/jimo.2007.3.223
[4]	Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499
[5]	Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125
[6]	Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779
[7]	S. Kanagawa, K. Inoue, A. Arimoto, Y. Saisho. Mean square approximation of multi dimensional reflecting fractional Brownian motion via penalty method. Conference Publications, 2005, 2005 (Special) : 463-475. doi: 10.3934/proc.2005.2005.463
[8]	Weipeng Hu, Zichen Deng, Yuyue Qin. Multi-symplectic method to simulate Soliton resonance of (2+1)-dimensional Boussinesq equation. Journal of Geometric Mechanics, 2013, 5 (3) : 295-318. doi: 10.3934/jgm.2013.5.295
[9]	Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775
[10]	Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057
[11]	Tatsien Li, Wancheng Sheng. The general multi-dimensional Riemann problem for hyperbolic systems with real constant coefficients. Discrete & Continuous Dynamical Systems - A, 2002, 8 (3) : 737-744. doi: 10.3934/dcds.2002.8.737
[12]	Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228
[13]	Franz Achleitner, Anton Arnold, Eric A. Carlen. On multi-dimensional hypocoercive BGK models. Kinetic & Related Models, 2018, 11 (4) : 953-1009. doi: 10.3934/krm.2018038
[14]	Anatoli F. Ivanov. On global dynamics in a multi-dimensional discrete map. Conference Publications, 2015, 2015 (special) : 652-659. doi: 10.3934/proc.2015.0652
[15]	Gerald Sommer, Di Zang. Parity symmetry in multi-dimensional signals. Communications on Pure & Applied Analysis, 2007, 6 (3) : 829-852. doi: 10.3934/cpaa.2007.6.829
[16]	Kang-Ling Liao, Chih-Wen Shih, Chi-Jer Yu. The snapback repellers for chaos in multi-dimensional maps. Journal of Computational Dynamics, 2018, 5 (1&2) : 81-92. doi: 10.3934/jcd.2018004
[17]	Yuzhong Zhang, Fan Zhang, Maocheng Cai. Some new results on multi-dimension Knapsack problem. Journal of Industrial & Management Optimization, 2005, 1 (3) : 315-321. doi: 10.3934/jimo.2005.1.315
[18]	Zhong-Zhi Bai. On convergence of the inner-outer iteration method for computing PageRank. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 855-862. doi: 10.3934/naco.2012.2.855
[19]	Paola Favati, Grazia Lotti, Ornella Menchi, Francesco Romani. An inner-outer regularizing method for ill-posed problems. Inverse Problems & Imaging, 2014, 8 (2) : 409-420. doi: 10.3934/ipi.2014.8.409
[20]	Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-9. doi: 10.3934/jimo.2018136

2018 Impact Factor: 1.025

American Institute of Mathematical Sciences