Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций
Конференция: Цифровые, компьютерные и информационные технологии в науке и образовании; Брянск; Брянск
Год издания: 2026
Ключевые слова: задача о рюкзаке, многомерная задача о рюкзаке, квадратичная задача о рюкзаке, генератор синтетических примеров
Аннотация: Задача о рюкзаке является одной из наиболее известных и популярных в научном сообществе задач комбинаторной оптимизации, которая, будучи NP-трудной не может быть решена за полиномиальное время, что делает ее трудноразрешимой при больших размерностях условий задачи или же при необходимости работать в реальном времени. В то же время Показать полностьюданная задача имеет достаточно большое число практических применений: в логистике, производстве, а также в различных технических системах, например в оптимизации трехмерного рендер-конвейера. У оригинальной постановки задачи о рюкзаке, которая состоит из одномерных весов и линейной функции ценности предметов в рюкзаке есть множество разнообразных вариаций, которые актуализируют условия задачи под другие проблемные области. Одной из самых слабо исследованных разновидностей задачи о рюкзаке является квадратичная задача о рюкзаке с многомерными весовыми ограничениями. Данная вариация задачи о рюкзаке имеет только одну основополагающую работу, выпущенную в далеком 2012 году, также в открытом доступе нет наборов тестовых примеров данной задачи и бенчмарков. Настоящая работа посвящена разработке и тестированию генератора синтетических примеров данной задачи, которые в дальнейшем будут использованы при разработке различных алгоритмических и эвристических решений для нее.
Журнал: Цифровые, компьютерные и информационные технологии в науке и образовании
Номера страниц: 245-249
Место издания: Брянск