Аппроксимационные схемы для задачи об упаковке в контейнеры: различия между версиями

В [[задача об упаковке в контейнеры|задаче об упаковке в контейнеры]] входными данными является набор предметов, определяемых их размерами. Также имеются одинаковые контейнеры, размеры которых без потери общности можно считать равными 1. Цель состоит в том, чтобы упаковать заданные предметы, используя минимально возможное количество контейнеров.

Упаковка контейнеров является классической оптимизационной задачей, и сотни ее вариантов были определены и изучены для различных условий, таких как анализ среднего случая, анализ наихудшего случая в оффлайновом режиме и анализ наихудшего случая в онлайновом режиме. Далее рассматривается самый простой вариант, упомянутый выше, в рамках оффлайновой модели, когда все предметы заданы заранее. Легко убедиться, что эта задача является NP-трудной, с помощью редукции задачи разбиения. Фактически такая редукция означает, что за исключением случая P = NP невозможно за полиномиальное время определить, можно ли упаковать предметы в два контейнера или их нужно будет три.

Исходными данными для задачи упаковки в контейнеры является набор <math>I</math> из n предметов, заданных их размерами <math>s_1, ..., s_n</math>, где каждый размер <math>s_i</math> представляет собой вещественное число в диапазоне (0, 1]. Подмножество предметов <math>S \subseteq I</math> может быть упаковано в контейнер, если суммарный размер предметов в S не превышает 1. Задача заключается в том, чтобы упаковать все предметы из <math>I</math> в минимальное количество контейнеров. Обозначим за OPT(I) величину оптимального решения, а за Size(I) – общий размер всех предметов в <math>I</math>. Очевидно, что <math>OPT(I) \ge \lceil Size(I) \rceil</math>.

Строго говоря, для этой задачи не допускается наличие алгоритма полиномиального времени с гарантией аппроксимации лучше 3/2. Любопытно, однако, что это не исключает существования алгоритма, требующего, скажем, OPT(I) + 1 контейнеров (в отличие от других задач оптимизации, в случае упаковки в контейнеры создание нескольких копий маленького «сложного экземпляра задачи» для получения сложного экземпляра большей величины не работает). Более осмысленно рассматривать гарантии аппроксимации в асимптотическом смысле.

В шестидесятых и семидесятых годах было разработано несколько алгоритмов с асимптотическими и абсолютными гарантиями аппроксимации, с постоянным коэффициентом и очень эффективным временем работы (см. обзор в [1]). Прорыв был достигнут в 1981 году де ла Вегой и Люкером [3], которые предложили первую полиномиальную по времени асимптотическую аппроксимационную схему.

Подход де ла Веги и Люкера [3] заключался в том, чтобы предложить технику аппроксимации исходного экземпляра более простым экземпляром, в котором крупные предметы могут иметь только O(1) различных размеров. Их идея была проста. Во-первых, достаточно ограничить внимание крупными предметами, скажем, размером больше <math>\varepsilon</math>. Обозначим этот набор <math>I_b</math>. Пусть имеется (почти) оптимальная упаковка для <math>I_b</math>; рассмотрим решение, полученное путем жадного заполнения контейнеров оставшимися мелкими предметами, открывая новые контейнеры только в случае необходимости. Действительно, если новые контейнеры не потребуются, то решение по-прежнему остается почти оптимальным, поскольку упаковка для <math>I_b</math> была почти оптимальной. Если же дополнительные контейнеры необходимы, то каждый контейнер (возможно, за исключением одного) должен быть заполнен до объема <math>(1 - \epsilon)</math>, что дает упаковку с использованием <math>Size(I)/(1 - \epsilon) + 1 \le OPT(I)/(1 - \epsilon) + 1</math> контейнеров. Таким образом, достаточно сосредоточиться на решении задачи <math>I_b</math> почти оптимальным способом. Для этого авторы показывают, как получить другой экземпляр задачи <math>I'</math> со следующими свойствами. Во-первых, в <math>I'</math> имеется только <math>O(1 / \epsilon^2)</math> различных размеров, во-вторых, <math>I'</math> является приближением <math>I_b</math> в том смысле, что <math>OPT(I_b) \ge OPT(I')</math> – и, более того, любое решение <math>I'</math> подразумевает решение <math>I_b</math> с использованием <math>O(\epsilon \cdot OPT(I))</math> дополнительных контейнеров. Поскольку в задаче <math>I'</math> имеется только <math>1 / \epsilon^2</math> различных размеров элементов, а в любой контейнер можно поместить не более <math>1 / \epsilon</math> таких элементов, существует не более <math>O(1 / \epsilon^2)^{1 / \epsilon}</math> способов упаковки в контейнеры. Таким образом, задача <math>I'</math> может быть решена оптимально путем исчерпывающего перечисления (или еще более эффективно с помощью описанной ниже формулировки целочисленного программирования).

Отправной точкой является экспоненциально большая релаксация линейного программирования (LP) данной задачи, обычно называемая конфигурационной линейной программой. Здесь имеется переменная <math>x_S</math>, соответствующая каждому подмножеству предметов S, которые можно подходящим образом упаковать в контейнер. Задача состоит в минимизации <math>\sum_S x_S</math> при условии, что для каждого предмета i сумма <math>x_S</math> по всем подмножествам S, содержащим i, не меньше 1. Очевидно, что это релаксация, поскольку задание соотношения <math>x_S = 1</math> для каждого набора S, соответствующего контейнеру в оптимальном решении, является допустимым целочисленным решением задачи LP. Несмотря на то, что в этой формулировке решение имеет экспоненциальную величину, задача разделения для двойственной формулировки является задачей о рюкзаке, и поэтому LP может быть решена за полиномиальное время с любой точностью (в частности, с точностью до 1) методом эллипсоидов. Такое решение называется дробно-линейной упаковкой. Заметим, что если имеется <math>n_i</math> предметов, каждый из которых имеет размер ровно <math>s_i</math>, то ограничения, соответствующие i, можно «объединить», чтобы получить следующий вариант LP:

<math>min \sum_S x_S</math>, такой, что <math>\sum_S a_{S, i} x_S \ge n_i</math> для всех размеров предметов i, <math>x_S \ge 0</math> для всех допустимых множеств S.

Здесь <math>a_{S,i}</math> – количество предметов размера <math>s_i</math> в допустимом множестве S. Обозначим за <math>q(I)</math> количество различных размеров в наборе <math>I</math>. Количество нетривиальных ограничений в LP равно <math>q(I)</math>, что означает, что существует базовое оптимальное решение этой линейной программы, в котором только <math>q(I)</math> переменных заданы нецелыми. Кармаркар и Карп используют это наблюдение весьма нетривиальным способом. Следующая лемма описывает их основную идею.

'''Лемма 3'''. Для любого заданного экземпляра J предположим, что существует алгоритмическая процедура округления для получения другого экземпляра J', такого, что в J' имеется Size(J)/2 различных размеров элементов, и J и J' связаны в следующем смысле: любая дробно-линейная упаковка J с использованием <math>\ell</math> контейнеров позволяет получить дробно-линейную упаковку J' с не более чем <math>\ell'</math> контейнерами, а любая упаковка J' с использованием <math>\ell'</math> контейнеров позволяет получить упаковку J с использованием <math>\ell' + c</math> контейнеров, где <math>c</math> – некоторый фиксированный параметр. Затем J может быть упакована с использованием OPT(J) + c <math>\cdot</math> log(OPT(J)) контейнеров.

Остается описать процедуру округления. Рассмотрим элементы в неубывающем порядке <math>s_1 \ge s_2 \ge ... \ge s_n</math> и сгруппируем их следующим образом. Добавляем элементы в текущую группу до тех пор, пока ее размер впервые не превысит 2. В этот момент закрываем группу и начинаем новую. Обозначим за <math>G_1, ..., G_k</math> сформированные группы и положим <math>n_i = |G_i|</math>, для удобства задав <math>n_0 = 0</math>. Определим <math>I'</math> как экземпляр, полученный округлением размера <math>n_{i - 1}</math> наибольших элементов в <math>G_i</math> до размера наибольшего элемента в <math>G_i</math> для i = 1, ..., k. Процедура удовлетворяет свойствам леммы 3 при <math>c = O(log \; n_k)</math>. Для доказательства Теоремы 2 достаточно показать, что <math>n_k = O(Size(I))</math>. Это легко сделать, игнорируя все элементы меньше <math>1/Size(I)</math> и заполняя их только в конце (подобно алгоритму де ла Веги и Люкера).

'''Следствие 1'''. Если все размеры элементов не меньше <math>\delta</math>, то легко заметить, что <math>c = O(log \; 1 / \delta)</math>, и приведенный выше алгоритм имеет гарантию <math>OPT+ O(log(1  / \delta) \cdot log \; OPT)</math>, что соответствует <math>OPT+ O(log \; OPT)</math>, если <math>\delta</math> – константа.

Помимо NP-трудности, другие показатели трудности не известны; возможно, что для данной задачи существует алгоритм с полиномиальным временем выполнения и гарантией OPT + 1. Решение этой задачи является ключевым открытым вопросом. Перспективным представляется подход с использованием упомянутой выше конфигурационной LP. На самом деле, не известно ни одного экземпляра задачи, для которого аддитивный разрыв между оптимальным решением конфигурационной линейной программы и оптимальным целочисленным решением был бы больше 1. Было бы любопытно спроектировать экземпляр, для которого аддитивный разрыв целостности был бы равен двум или более.

Гарантия Кармаркара и Карпа <math>OPT + O(log^2 \; OPT)</math> была самым известным результатом за последние 25 лет, и любое улучшение этой оценки само по себе было бы чрезвычайно интересным.