Быстрый алгоритм решения квадратичной задачи о ранце
DOI:
https://doi.org/10.21638/spbu01.2022.108Аннотация
В работе рассматривается задача квадратичного программирования со строго выпуклой сепарабельной целевой функцией, единственным линейным ограничением и двусторонними ограничениями на переменные. В англоязычной литературе эта задача называется Convex Knapsack Separable Quadratic Problem, или сокращенно - CKSQP. Нас интересует алгоритм решения задачи CKSQP с линейной сложностью. Посвященные этой теме работы содержат неточности в описании алгоритмов и неэффективные реализации. В данной работе удалось преодолеть имеющиеся трудности.Ключевые слова:
квадратичное программирование, задача о ранце, быстрые алгоритмы
Скачивания
Библиографические ссылки
Литература
References
Загрузки
Опубликован
Как цитировать
Выпуск
Раздел
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.