A two-phase method for solving continuous rank-one quadratic knapsack problems

Document Type : Research Article

Author

• S.E. Monabbati

Department of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran.

10.22067/ijnao.2022.70644.1096

Abstract

We propose a two-phase algorithm for solving continuous rank-one quadratic knapsack problems (R1QKPs). In particular, we study the solution structure of the problem without the knapsack constraint. In fact, an $O(n\log n)$ algorithm is suggested in this case. We then use the solution structure to propose an $O(n^2\log n)$ algorithm that finds an interval containing the optimal value of the Lagrangian dual of R1QKP. In the second phase, we solve the Lagrangian dual problem using a traditional single-variable optimization method. We perform a computational test on random instances and compare our algorithm with the general solver CPLEX.

Keywords

• Quadratic Knapsack Problem
• Line-Sweep Algorithm

Main Subjects

• Optimization

---

References

1. Bitran, G.R. and Hax, A.C.Disaggregation and resource allocation using convex knapsack problems with bounded variables, Management Sci. 27(4) (1981) 431–441.

2. Brucker, P. An O(n) algorithm for quadratic knapsack problems, Oper. Res. Lett. 3(3) (1984) 163–166.
3. Cominetti, R., Mascarenhas, W.F. and Silva, P.J.S. A Newton’s method for the continuous quadratic knapsack problem, Math. Program. Comput. 6(2) (2014) 151–169.

4. Dai, Y-H. and Fletcher, R. New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds, Math. Program. 106(3) (2006) 403–421.

5. de Berg, M., Cheong, O., van Kreveld, M. and Overmars, M. Compu-tational geometry. Algorithms and applications. Third edition. Springer-Verlag, Berlin, 2008.

6. di Serafino, D., Toraldo, G., Viola, M. and Barlow, J. A two-phase gra-dient method for quadratic programming problems with a single linear constraint and bounds on the variables, SIAM J. Optim. 28(4) (2018) 2809–2838.

7. Dussault, J-P., Ferland, J.A. and Lemaire, B. Convex quadratic program-ming with one constraint and bounded variables, Math. Program. 36(1)(1986) 90–104.

8. Fletcher, R. Augmented lagrangians, box constrained QP and extensions, IMA J. Numer. Anal. 37(4) (2017) 1635–1656.

9. Helgason, R., Kennington, J. and Lall, H. A polynomially bounded algo-rithm for a singly constrained quadratic program, Math. Program. 18(3)(1980) 338–343.

10. IBM, Cplex performance tuning for quadratic programs,

https://www.ibm.com/support/pages/node/397129?mhsrc=ibmsearch_a&mhq=CPLEXPerformanceTuningforQuadraticPrograms, June 2018, [Online; accessed 23-January-2022].

11. Liu, M. and Liu, Y-J. Fast algorithm for singly linearly constrained quadratic programs with box-like constraints, Comput. Optim. Appl. 66(2) (2017) 309–326.

12. Pardalos, P.M., Ye, Y., and Han, C-G. Algorithms for the solution of quadratic knapsack problems, Linear Algebra Appl. 152 (1991), 69–91.

13. Patriksson, M. A survey on the continuous nonlinear resource allocation problem, European J. Oper. Res. 185(1) (2008) 1–46.

14. Patriksson, M. and Strömberg, C. Algorithms for the continuous non-linear resource allocation problem—new implementations and numerical studies, European J. Oper. Res. 243(3) (2015) 703–722.

15. Robinson, A.G., Jiang, N. and Lerme, C.S. On the continuous quadratic knapsack problem, Math. program. 55(1-3) (1992) 99–108.

16. Sharkey, T.C. and Romeijn, H.E. A class of nonlinear nonseparable con-tinuous knapsack and multiple-choice knapsack problems, Math. Program. 126(1) (2011) 69–96.