Open AccessFast algorithm for quadratic knapsack problem
Author(s) -
Artyom V. Plotkin
Publication year - 2022
Publication title -
vestnik sankt-peterburgskogo universiteta. matematika. mehanika. astronomiâ/vestnik sankt-peterburgskogo universiteta. seriâ 1, matematika, mehanika, astronomiâ
Language(s) - English
Resource type - Journals
eISSN - 2587-5884
pISSN - 1025-3106
DOI - 10.21638/spbu01.2022.108
Subject(s) - knapsack problem , separable space , change making problem , quadratic programming , quadratic equation , mathematical optimization , mathematics , constraint (computer aided design) , function (biology) , regular polygon , algorithm , implementation , convex function , cutting stock problem , convex optimization , continuous knapsack problem , computer science , optimization problem , mathematical analysis , geometry , evolutionary biology , biology , programming language
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.