American Institute of Mathematical Sciences

Advanced
April  2007, 3(2): 223-232. doi: 10.3934/jimo.2007.3.223

An exact algorithm for 0-1 polynomial knapsack problems

Xiaoling Sun 1, , Hongbo Sheng 2, and  Duan Li 3,

1. 

Department of Management Science, School of Management, Fudan University, Shanghai 200433, P. R., China
2. 

Department of Elementary Education, Tongling University, Tongling, Anhui 244000, P. R., China
3. 

Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N. T., Hong Kong, China

Received  August 2006 Revised  January 2007 Published  April 2007

In this paper we propose an exact method for the 0-1 polynomial knapsack problem. The algorithm seeks the exact optimal solution of the problem by a back-tracking branch-and-bound procedure. The upper bounds are computed by a Lagrangian dual search where the Lagrangian relaxations are solved by the maximum-flow method. Heuristic procedures are derived to search for feasible solutions and thus to improve the performance of the algorithm. Promising computational results are reported for test problems with both single constraint and multiple constraints.
Keywords: Lagrangian relaxation, branch-and-bound method, 0-1 polynomial knapsack problem, maximum-flow algorithm..
Mathematics Subject Classification: Primary: 90C09; 90C10; Secondary: 90C3.
Citation: Xiaoling Sun, Hongbo Sheng, Duan Li. An exact algorithm for 0-1 polynomial knapsack problems. Journal of Industrial and Management Optimization, 2007, 3 (2) : 223-232. doi: 10.3934/jimo.2007.3.223
[1]

Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial and Management Optimization, 2013, 9 (3) : 531-547. doi: 10.3934/jimo.2013.9.531
[2]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104
[3]

Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044
[4]

Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial and 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 and Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125
[6]

Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial and Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647
[7]

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

Binghai Zhou, Yuanrui Lei, Shi Zong. Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021151
[9]

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 and Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779
[10]

R.L. Sheu, M.J. Ting, I.L. Wang. Maximum flow problem in the distribution network. Journal of Industrial and Management Optimization, 2006, 2 (3) : 237-254. doi: 10.3934/jimo.2006.2.237
[11]

Hsin-Min Sun, Yu-Juan Sun. Variable fixing method by weighted average for the continuous quadratic knapsack problem. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 15-29. doi: 10.3934/naco.2021048
[12]

Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial and Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71
[13]

Palash Sarkar, Shashank Singh. A unified polynomial selection method for the (tower) number field sieve algorithm. Advances in Mathematics of Communications, 2019, 13 (3) : 435-455. doi: 10.3934/amc.2019028
[14]

Konstantinos A. Draziotis, Anastasia Papadopoulou. Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme. Advances in Mathematics of Communications, 2018, 12 (3) : 429-449. doi: 10.3934/amc.2018026
[15]

Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030
[16]

Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial and Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775
[17]

Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial and Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136
[18]

Stephane Chretien, Paul Clarkson. A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids. Journal of Industrial and Management Optimization, 2020, 16 (1) : 431-443. doi: 10.3934/jimo.2018161
[19]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117
[20]

Yuxin Tan, Yijing Sun. The Orlicz Minkowski problem involving $ 0 < p < 1 $: From one constant to an infinite interval. Discrete and Continuous Dynamical Systems - S, 2021, 14 (6) : 1983-1994. doi: 10.3934/dcdss.2021037

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (439)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy