Многомерная задача о рюкзаке (MKP): суррогатная релаксация и агрегация ограничений

Математическая формулировка MKP описывается в терминах булевого (0-1) линейного программирования. Имеется набор из N предметов, каждый из которых имеет определенную полезность (ценность). Также имеется набор из M независимых ограничений (размерностей рюкзака), где каждое ограничение имеет свою максимальную вместимость. Переменные принятия решений являются бинарными: единица означает, что предмет включен в рюкзак, ноль — что предмет отвергнут. Целевая функция заключается в максимизации суммарной полезности выбранных предметов при жестком условии, что ни по одной из M размерностей суммарный расход ресурса не превышает заданного лимита. В отличие от одномерного случая, динамическое программирование здесь терпит полный крах (проклятие размерности), так как таблица мемоизации становится M-мерной и мгновенно переполняет память компьютера.

Для нахождения точного оптимального решения MKP исследователи операций используют метод ветвей и границ в сочетании с линейной релаксацией. На каждом узле дерева поиска требование целочисленности бинарных переменных временно отбрасывается (им разрешается принимать дробные значения от 0 до 1). Полученная задача непрерывного линейного программирования молниеносно решается симплекс-методом, выдавая верхнюю границу (Upper Bound) целевой функции. Если эта верхняя граница (включающая доли предметов) оказывается хуже, чем лучшее уже найденное чисто целочисленное решение, ветвь отсекается. Однако при большом количестве ограничений разрыв (Duality Gap) между дробным и целочисленным оптимумом становится настолько огромным, что дерево ветвления разрастается до астрономических размеров.

Грандиозным математическим инструментом для сжатия этого дерева является Суррогатная релаксация (Surrogate Relaxation), предложенная Фредом Гловером в 1968 году. Идея суррогатной релаксации заключается в агрегации (слиянии) множества ограничений в одно единственное сверх-ограничение. Алгоритм берет все M ограничений и складывает их в единое неравенство, предварительно умножив каждое ограничение на специальный весовой коэффициент (множитель). В результате сложная многомерная задача алгебраически схлопывается в классическую одномерную задачу о рюкзаке, которая решается за миллисекунды. Если правильно подобрать систему весовых множителей, суррогатная верхняя граница окажется математически намного более строгой (низкой), чем граница непрерывной линейной релаксации, что позволяет отсекать миллионы тупиковых ветвей.

Для практического (эвристического) решения MKP на сверхбольших данных применяются жадные алгоритмы с модифицированными коэффициентами полезности. В одномерном рюкзаке предметы сортируются по удельной ценности (ценность, деленная на вес). В многомерном рюкзаке вычисляется псевдо-удельная ценность (Pseudo-utility ratio). Вес каждого предмета рассчитывается как сумма потребляемых им ресурсов по всем размерностям, причем ресурсы, которые находятся в наибольшем дефиците в текущий момент, штрафуются самыми высокими весовыми коэффициентами. Предметы сортируются по этому скалярному соотношению, и алгоритм жадно набивает рюкзак, постоянно пересчитывая дефицитность оставшихся ресурсов на каждом шаге. Эта адаптивная эвристика гарантирует высокую плотность упаковки в облачных серверах и логистических хабах.