Быстрый алгоритм решения квадратичной задачи о ранце
DOI:
https://doi.org/10.21638/spbu01.2022.108Аннотация
В работе рассматривается задача квадратичного программирования со строго выпуклой сепарабельной целевой функцией, единственным линейным ограничением и двусторонними ограничениями на переменные. В англоязычной литературе эта задача называется Convex Knapsack Separable Quadratic Problem, или сокращенно - CKSQP. Нас интересует алгоритм решения задачи CKSQP с линейной сложностью. Посвященные этой теме работы содержат неточности в описании алгоритмов и неэффективные реализации. В данной работе удалось преодолеть имеющиеся трудности.Ключевые слова:
квадратичное программирование, задача о ранце, быстрые алгоритмы
Скачивания
Данные скачивания пока недоступны.
Библиографические ссылки
Литература
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).
Загрузки
Опубликован
10.04.2022
Как цитировать
Плоткин, А. В. (2022). Быстрый алгоритм решения квадратичной задачи о ранце. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 9(1), 76–84. https://doi.org/10.21638/spbu01.2022.108
Выпуск
Раздел
Математика
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.
