Аппроксимационные схемы для задачи об упаковке в контейнеры
Ключевые слова и синонимы
Задача раскроя
Постановка задачи
В задаче об упаковке в контейнеры входными данными является набор предметов, определяемых их размерами. Также имеются одинаковые контейнеры, размеры которых без потери общности можно считать равным 1. Цель состоит в том, чтобы упаковать заданные предметы, используя минимально возможное количество контейнеров.
Упаковка контейнеров является классической оптимизационной задачей, и сотни ее вариантов были определены и изучены для различных условий, таких как анализ среднего случая, анализ наихудшего случая в оффлайновом режиме и анализ наихудшего случая в онлайновом режиме. Далее рассматривается самый простой вариант, упомянутый выше, в рамках оффлайновой модели, когда все предметы заданы заранее. Легко убедиться, что эта задача является NP-полной, с помощью редукции задачи разбиения. Фактически такая редукция означает, что за исключением случая P = NP невозможно за полиномиальное время определить, можно ли упаковать предметы в два контейнера или их нужно будет три.
Нотация
Исходными данными для задачи упаковки в контейнеры является набор [math]\displaystyle{ I }[/math] из n предметов, заданных их размерами [math]\displaystyle{ s_1, ..., s_n }[/math], где каждый размер [math]\displaystyle{ s_i }[/math] представляет собой вещественное число в диапазоне (0, 1]. Подмножество предметов [math]\displaystyle{ S \subseteq I }[/math] может быть упаковано в контейнер, если общий размер предметов в S не превышает 1. Задача заключается в том, чтобы упаковать все предметы из I в минимальное количество контейнеров. Обозначим за OPT(I) значение оптимального решения, а за Size(I) – общий размер всех предметов в I. Очевидно, что [math]\displaystyle{ OPT(I) \ge \lceil Size(I) \rceil }[/math].
Строго говоря, для этой задачи не допускается наличие алгоритма полиномиального времени с гарантией аппроксимации лучше 3/2. Любопытно, однако, что это не исключает существования алгоритма, требующего, скажем, OPT(I) + 1 контейнеров (в отличие от других задач оптимизации, в случае упаковки в контейнеры создание нескольких копий маленького «сложного экземпляра задачи» для получения сложного экземпляра величины не работает). Более осмысленно рассматривать гарантии аппроксимации в асимптотическом смысле.
Алгоритм называется асимптотической [math]\displaystyle{ \rho }[/math]-аппроксимацией, если требующееся ему количество контейнеров равно [math]\displaystyle{ \rho \cdot OPT(I) + O(1) }[/math].
Основные результаты
В шестидесятых и семидесятых годах было разработано несколько алгоритмов с асимптотическими и абсолютными гарантиями аппроксимации, с постоянным коэффициентом и очень эффективным временем работы (см. обзор в [1]). Прорыв был достигнут в 1981 году де ла Вегой и Люкером [ ], которые предложили первую полиномиальную по времени асимптотическую аппроксимационную схему.
Теорема 1 [3]. Для любого произвольного параметра [math]\displaystyle{ \epsilon \gt 0 }[/math] существует алгоритм, использующий [math]\displaystyle{ (1 + \epsilon)OPT(I) + O(1) }[/math] контейнеров для упаковки набора [math]\displaystyle{ I }[/math]. Время работы этого алгоритма составляет [math]\displaystyle{ O(n \; log \; n) + (1 / \epsilon)^{O(1 / \epsilon)} }[/math].
Подход де ла Веги и Люкера [3] заключался в том, чтобы предложить технику аппроксимации исходного экземпляра более простым экземпляром, в котором крупные предметы могут иметь только O(1) различных размеров. Их идея была проста. Во-первых, достаточно ограничить внимание крупными предметами, скажем, размером больше [math]\displaystyle{ \varepsilon }[/math]. Обозначим эту новую задачу [math]\displaystyle{ I_b }[/math]. Пусть имеется (почти) оптимальная упаковка для [math]\displaystyle{ I_b }[/math]; рассмотрим решение, полученное путем жадного заполнения контейнеров оставшимися мелкими предметами, открывая новые контейнеры только в случае необходимости. Действительно, если новые контейнеры не потребуются, то решение по-прежнему остается почти оптимальным, поскольку упаковка для [math]\displaystyle{ I_b }[/math] была почти оптимальной. Если же дополнительные контейнеры необходимы, то каждый контейнер (возможно, за исключением одного) должен быть заполнен до объема [math]\displaystyle{ (1 - \epsilon) }[/math], что дает упаковку с использованием [math]\displaystyle{ Size(I)/(1 - \epsilon) + 1 \le OPT(I)/(1 - \epsilon) + 1 }[/math] контейнеров. таким образом, достаточно сосредоточиться на решении задачи [math]\displaystyle{ I_b }[/math] почти оптимальным образом. Для этого авторы показывают, как получить другой экземпляр задачи [math]\displaystyle{ I' }[/math] со следующими свойствами. Во-первых, в [math]\displaystyle{ I' }[/math] имеется только [math]\displaystyle{ O(1 / \epsilon^2) }[/math] различных размеров, во-вторых, [math]\displaystyle{ I_b }[/math]I0 является приближением [math]\displaystyle{ I_b }[/math] в том смысле, что [math]\displaystyle{ OPT(I_b) \ge OPT(I') }[/math] – и, более того, любое решение [math]\displaystyle{ I' }[/math] подразумевает решение [math]\displaystyle{ I_b }[/math] с использованием [math]\displaystyle{ O(\epsilon \cdot OPT(I)) }[/math] дополнительных контейнеров. Поскольку в задаче [math]\displaystyle{ I' }[/math] имеется только [math]\displaystyle{ 1 / \epsilon^2 }[/math] различных размеров элементов, а в любой контейнер можно поместить не более [math]\displaystyle{ 1 / \epsilon }[/math] таких элементов, существует не более [math]\displaystyle{ O(1 / \epsilon^2)^{1 / \epsilon} }[/math] способов упаковки в контейнеры. Таким образом, задача [math]\displaystyle{ I' }[/math] может быть решена оптимально путем исчерпывающего перечисления (или еще более эффективно с помощью описанной ниже формулировки целочисленного программирования).
Позже Кармаркар и Карп [4] доказали существенно более сильную гарантию.
Теорема 2 [4]. Для экземпляра задачи [math]\displaystyle{ I }[/math] существует алгоритм, который производит упаковку [math]\displaystyle{ I }[/math] с использованием [math]\displaystyle{ OPT(I) + O(log^2 \; OPT(I)) }[/math] контейнеров. Время выполнения этого алгоритма составляет [math]\displaystyle{ O(n^8) }[/math].
Обратите внимание, что эта гарантия значительно сильнее, чем в работе [3], так как в нее входит аддитивный член [math]\displaystyle{ O(log^2 \; OPT) }[/math], а не [math]\displaystyle{ O(\epsilon \cdot OPT) }[/math]. В этом алгоритме также используется идея уменьшения количества различных размеров элементов и игнорирования маленьких элементов, но гораздо более тонким образом. В частности, вместо того чтобы получить округленный экземпляр за один шаг, алгоритм состоит из логарифмического числа шагов, на каждом из которых авторы «слегка» округляют экземпляр, а затем частично решают его.
Отправной точкой является экспоненциально большая релаксация линейного программирования (LP) данной задачи, обычно называемая конфигурационной линейной программой. Здесь имеется переменная [math]\displaystyle{ x_S }[/math], соответствующая каждому подмножеству предметов S, которые можно подходящим образом упаковать в контейнер. Задача состоит в минимизации [math]\displaystyle{ \sum_S x_S }[/math] при условии, что для каждого предмета i сумма [math]\displaystyle{ x_S }[/math] по всем подмножествам S, содержащим i, не меньше 1. Очевидно, что это релаксация, поскольку задание соотношения [math]\displaystyle{ x_S = 1 }[/math] для каждого набора S, соответствующего контейнеру в оптимальном решении, является допустимым целочисленным решением задачи LP. Несмотря на то, что в этой формулировке решение имеет экспоненциальный размер, задача разделения для двойственной формулировки является задачей о рюкзаке, и поэтому LP может быть решена за полиномиальное время с любой точностью (в частности, с точностью до 1) методом эллипсоидов. Такое решение называется дробно-линейной упаковкой. Заметим, что если имеется [math]\displaystyle{ n_i }[/math] предметов, каждый из которых имеет размер ровно [math]\displaystyle{ s_i }[/math], то ограничения, соответствующие i, можно «объединить», чтобы получить следующий вариант LP:
[math]\displaystyle{ min \sum_S x_S }[/math], такой, что [math]\displaystyle{ \sum_S a_{S, i} x_S \ge n_i \; \forall }[/math] размеров предметов i, [math]\displaystyle{ x_S \ge 0 \; \forall }[/math] допустимых множеств S.
Здесь [math]\displaystyle{ a_{S,i} }[/math] – количество предметов размера [math]\displaystyle{ s_i }[/math] в допустимом множестве S. Обозначим за [math]\displaystyle{ q(I) }[/math] количество различных размеров в наборе [math]\displaystyle{ I }[/math]. Число нетривиальных ограничений в LP равно [math]\displaystyle{ q(I) }[/math], что означает, что существует базовое оптимальное решение этой линейной программы, в котором только [math]\displaystyle{ q(I) }[/math] переменных заданы нецелочисленными. Кармаркар и Карп используют это наблюдение весьма нетривиальным способом. Следующая лемма описывает их основную идею.
Лемма 3. Для любого заданного экземпляра J предположим, что существует алгоритмическая процедура округления для получения другого экземпляра J', такого, что в J' имеется Size(J)/2 различных размеров элементов, и J и J' связаны в следующем смысле: любая дробно-линейная упаковка J с использованием [math]\displaystyle{ \ell }[/math] контейнеров позволяет получить дробно-линейную упаковку J' с не более чем [math]\displaystyle{ \ell }[/math] контейнерами, а любая упаковка J' с использованием [math]\displaystyle{ \ell' }[/math] контейнеров позволяет получить упаковку J с использованием [math]\displaystyle{ \ell + c }[/math] контейнеров, где c – некоторый фиксированный параметр. Затем J может быть упакована с использованием OPT(J) + c [math]\displaystyle{ \cdot }[/math] log(OPT(J)) контейнеров.
Доказательство. Пусть [math]\displaystyle{ I_0 = I }[/math] и пусть [math]\displaystyle{ I_1 }[/math] – экземпляр, полученный в результате применения процедуры округления к [math]\displaystyle{ I_0 }[/math]. Согласно свойству процедуры округления, [math]\displaystyle{ OPT(I) \le OPT(I_1) + c }[/math] и [math]\displaystyle{ LP(I_1) \le LP(I) }[/math]. Поскольку в [math]\displaystyle{ I_1 }[/math] имеется [math]\displaystyle{ Size(I_0)/2 }[/math] различных размеров, решение LP для [math]\displaystyle{ I_1 }[/math] имеет не более [math]\displaystyle{ Size(I_0)/2 }[/math] дробно заданных переменных. Удалим элементы, упакованные в LP-решении цельным образом, и рассмотрим остаточный экземпляр [math]\displaystyle{ I'_1 }[/math]. Заметим, что [math]\displaystyle{ Size(I'_1) \le Size(I_0)/2 }[/math]. Теперь заново применим процедуру округления к [math]\displaystyle{ I'_1 }[/math], чтобы получить [math]\displaystyle{ I_2 }[/math], и решим задачу LP для [math]\displaystyle{ I_2 }[/math]. И вновь это решение имеет не более [math]\displaystyle{ Size(I'_1)/2 \le Size(I_0)/4 }[/math] дробно заданных переменных, при этом [math]\displaystyle{ OPT(I'_1) \le OPT(I_2) + c }[/math] и [math]\displaystyle{ LP(I_2) \le LP(I'_1) }[/math]. Вышеописанный процесс повторяется на протяжении нескольких шагов. На каждом шаге размер остаточного экземпляра уменьшается не менее чем в два раза, а количество контейнеров, необходимых для упаковки I0, увеличивается на аддитивную величину c. После log(Size(I0)) (?rf log(OPT(I))) шагов остаточный экземпляр имеет размер O(1) и может быть упакован в O(1) дополнительных контейнеров. □
Остается описать процедуру округления. Рассмотрим элементы в неубывающем порядке s1 > s2 > … > sn и сгруппируем их следующим образом. Добавляем элементы в текущую группу до тех пор, пока ее размер впервые не превысит 2. В этот момент закрываем группу и начинаем новую. Обозначим за G1... Gk сформированные группы и положим ni = jGij, для удобства задав щ = 0. Определим I0 как экземпляр, полученный округлением размера "i_i наибольших элементов в Gi до размера наибольшего элемента в Gi для i = 1; : : : ; k. Процедура удовлетворяет свойствам леммы 3 при c = O(log щ). Для доказательства Теоремы 2 достаточно показать, что щ = O(Size(I)). Это легко сделать, игнорируя все элементы меньше 1/Size(I) и заполняя их только в конце (подобно алгоритму де ла Веги и Люкера).
В случае, когда размеры элементов не слишком малы, получаем следующее следствие.
Следствие 1. Если все размеры элементов не меньше S, то легко видеть, что c = O(log 1/(5), и приведенный выше алгоритм гарантирует OPT+ 0(log(l/<5) -logOPT), что соответствует OPT+ O(logOPT), если S – константа.
Применение
Задача упаковки в контейнеры непосредственно мотивирована практикой и имеет множество естественных приложений, таких как упаковка предметов в коробки с учетом ограничений на вес, укладывание файлов на компакт-диски, упаковка рекламных роликов в перерывы между телепередачами и так далее. Она широко изучается в сфере исследования операций и компьютерных наук. Другие варианты применения включают так называемые задачи раскроя, когда некоторый материал, например ткань или пиломатериалы, дается в виде блоков стандартного размера, из которых нужно вырезать изделия определенного размера. Также были подробно изучены некоторые вариации задачи упаковки в контейнеры, такие как обобщение на более высокие размерности, наложение дополнительных ограничений на алгоритм и различные критерии оптимизации. Отличные обзоры таких исследований можно найти в работах [1, 2].
Открытые вопросы
Помимо NP-трудности, другие показатели трудности не известны; возможно, что для данной задачи существует алгоритм с полиномиальным временем выполнения и гарантией OPT + 1. Решение этой задачи является ключевым открытым вопросом. Перспективным представляется подход с использованием упомянутой выше конфигурационной LP. На самом деле, не известно ни одного экземпляра задачи, для которого аддитивный разрыв между оптимальным решением конфигурационной ЛП и оптимальным целочисленным решением был бы больше 1. Было бы очень интересно спроектировать экземпляр, для которого аддитивный разрыв целостности был бы равен двум или более.
Гарантия Кармаркара и Карпа OPT + O(log2 OPT) была самым известным результатом за последние 25 лет, и любое улучшение этой оценки само по себе было бы чрезвычайно интересным.
См. также
Литература
1. Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems, pp. 46-93. PWS, Boston (1996)
2. Csirik,J., Woeginger, G.: On-line packing and covering problems. In: Fiat, A., Woeginger, G. (eds.) Online Algorithms: The State of theArt.LNCS,vol. 1442, pp. 147-177. Springer, Berlin (1998)
3. Fernandez de la Vega, W., Lueker, G.: Bin packing can be solved within 1 + " in linear time. Combinatorica 1, 349-355 (1981)
4. Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science (FOCS), 1982, pp. 312-320