Fast algorithm for quadratic knapsack problem

Authors

  • Artyom V. Plotkin St Petersburg State University, 7–9, Universitetskaya nab., St Petersburg, 199034, Russian Federation

DOI:

https://doi.org/10.21638/spbu01.2022.108

Abstract

The paper considers a quadratic programming problem with a strictly convex separable objective function, a single linear constraint, and two-sided constraints on variables. This problem is commonly called the Convex Knapsack Separable Quadratic Problem, or CKSQP for short. We are interested in an algorithm for solving CKSQP with a linear time complexity. The papers devoted to this topic contain inaccuracies in the description of algorithms and ineffective implementations. In this work, the existing difficulties were overcome.

Keywords:

quadratic programming, knapsack problem, fast algorithms

Downloads

Download data is not yet available.
 

References

Литература

1. Jeong J. Indefinite Knapsack Separable Quadratic Programming: Methods and Applications. Dr. Sci. thesis (2014).

2. Kiwiel K. Breakpoint searching algorithms for the continuous quadratic knapsack problem. Mathematical Programming 112, 473–491 (2008). https://doi.org/10.1007/s10107-006-0050-z

3. Dai Y.H., Fletcher R. New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Mathematical Programming 106, 403–421 (2006). https://doi.org/10.1007/s10107-005-0595-2

4. Nielsen S., Zenios S. Massively parallel algorithms for singly-constrained convex programs. ORSA J. Comput. 4, 166–181 (1992). https://doi.org/10.1287/ijoc.4.2.166

5. Patriksson M. A survey on the continuous nonlinear resource allocation problem. European J. Operational Research 185, 1–46 (2008). https://doi.org/10.1016/j.ejor.2006.12.006

6. Calamai P., Mor´e J. Quasi-Newton updates with bounds. SIAM J. Numer. Anal. 24, 1434–1441 (1987).

7. Малозёмов В.Н., Тамасян Г.Ш. Представления непрерывных кусочно-аффинных функций. В: Семинар ¾CNSA & NDO¿. Избранные доклады. 10 сентября 2019 г. (2019).

8. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ, пер. с англ. 3-е изд. Вильямс (2013).

9. Frangioni A., Gorgone E. A library for continuous convex separable quadratic knapsack problems. European J. Operational Research 229, 37–40 (2013). https://doi.org/10.1016/j.ejor.2013.02.038

10. GitHub. Доступно на: https://github.com/WhatElseIsThere/CKSQP (дата обращения: 30.11.2021).

References

1. Jeong J. Indefinite Knapsack Separable Quadratic Programming: Methods and Applications. Dr. Sci. thesis (2014).

2. Kiwiel K. Breakpoint searching algorithms for the continuous quadratic knapsack problem. Mathematical Programming 112, 473–491 (2008). https://doi.org/10.1007/s10107-006-0050-z

3. Dai Y.H., Fletcher R. New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Mathematical Programming 106, 403–421 (2006). https://doi.org/10.1007/s10107-005-0595-2

4. Nielsen S., Zenios S. Massively parallel algorithms for singly-constrained convex programs. ORSA J. Comput. 4, 166–181 (1992). https://doi.org/10.1287/ijoc.4.2.166

5. Patriksson M. A survey on the continuous nonlinear resource allocation problem. European J. Operational Research 185, 1–46 (2008). https://doi.org/10.1016/j.ejor.2006.12.006

6. Calamai P., Mor´e J. Quasi-Newton updates with bounds. SIAM J. Numer. Anal. 24, 1434–1441 (1987).

7. Malozemov V.N., Tamasyan G. S. Representations of continuous piecewise affine functions. In: Seminar “CNSA & NDO”. Selected reports. Sept. 10, 2019 (2019). (In Russian)

8. Cormen T.H., Leiserson C.E., Rivest R. L., Stein C. Introduction to Algorithms. 3rd ed. The MIT Press (2009). [Rus. ed.: Cormen T.H., Leiserson C.E., Rivest R. L., Stein C. Algoritmy. Postroenie i analiz. Williams Publ. (2013)].

9. Frangioni A., Gorgone E. A library for continuous convex separable quadratic knapsack problems. European J. Operational Research 229, 37–40 (2013). https://doi.org/10.1016/j.ejor.2013.02.038

10. GitHub. Available at: https://github.com/WhatElseIsThere/CKSQP (accessed: November 30, 2021).

Downloads

Published

2022-04-10

How to Cite

Plotkin, A. V. (2022). Fast algorithm for quadratic knapsack problem. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 9(1), 76–84. https://doi.org/10.21638/spbu01.2022.108

Issue

Vol. 9 No. 1 (2022)

Section

Mathematics

License

Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.