Аппроксимационные схемы для задачи об упаковке в контейнеры
Ключевые слова и синонимы
Задача раскроя
Постановка задачи
В задаче об упаковке в контейнеры входными данными является набор предметов, определяемых их размерами. Также имеются одинаковые контейнеры, размеры которых без потери общности можно считать равным 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]. Для экземпляра задачи I существует алгоритм, который производит упаковку I с использованием OPT(I) + O(log2 OPT(I)) контейнеров. Время исполнения этого алгоритма составляет O(n8).
Обратите внимание, что эта гарантия значительно сильнее, чем в работе [ ], так как в нее входит аддитивный член O(log2 OPT), а не O(e - OPT). В этом алгоритме также используется идея уменьшения количества различных размеров элементов и игнорирования маленьких элементов, но гораздо более тонким образом. В частности, вместо того чтобы получить округленный экземпляр за один шаг, алгоритм состоит из логарифмического числа шагов, на каждом из которых авторы «слегка» округляют экземпляр, а затем частично решают его.
Отправной точкой является экспоненциально большая релаксация линейного программирования (LP) данной задачи, обычно называемая конфигурационной линейной программой. Здесь имеется переменная xS, соответствующая каждому подмножеству товаров S, которые можно подходящим образом упаковать в контейнер. Задача состоит в минимизации PS xS при условии, что для каждого предмета i сумма xS по всем подмножествам S, содержащим i, не меньше 1. Очевидно, что это релаксация, поскольку задание соотношения xS = 1 для каждого набора S, соответствующего контейнеру в оптимальном решении, является допустимым целочисленным решением задачи LP. Несмотря на то, что в этой формулировке решение имеет экспоненциальный размер, задача разделения для двойственной формулировки является задачей о рюкзаке, и поэтому LP может быть решена за полиномиальное время с любой точностью (в частности, с точностью до 1) методом эллипсоидов. Такое решение называется дробно-линейной упаковкой. Заметим, что если имеется ni предметов, каждый из которых имеет размер ровно si, то ограничения, соответствующие i, можно «объединить», чтобы получить следующий вариант LP:
Здесь aS,i – количество предметов размера si в допустимом множестве S. Обозначим за q(I) количество различных размеров в наборе I. Число нетривиальных ограничений в LP равно q(I), что означает, что существует базовое оптимальное решение этой линейной программы, в котором только q(I) переменных заданы нецелочисленными. Кармаркар и Карп используют это наблюдение весьма нетрививальным способом. Следующая лемма описывает их основную идею.
Лемма 3. Для любого заданного экземпляра J предположим, что существует алгоритмическая процедура округления для получения другого экземпляра J0, такого, что в J0 имеется Size(J)/2 различных размеров элементов, и J и J0 связаны в следующем смысле: любая дробно-линейная упаковка J с использованием I контейнеров позволяет получить дробно-линейную упаковку J0 с не более чем I контейнерами, а любая упаковка J0 с использованием I' контейнеров позволяет получить упаковку J с использованием I' + c контейнеров, где c – некоторый фиксированный параметр. Затем J может быть упакована с использованием OPT(J) + c ■ log(OPT(J)) контейнеров.
Доказательство. Пусть I0 = I и пусть I1 – экземпляр, полученный в результате применения процедуры округления к I0. Согласно свойству процедуры округления, OPT(I) < OPT(I1) + c и LP(I1) < LP(I). Поскольку в h имеется Size(I0)/2 различных размеров, решение LP для I1 имеет не более Size(I0)/2 дробно заданных переменных. Удалим элементы, упакованные в LP-решении цельным образом, и рассмотрим остаточный экземпляр I10. Заметим, что Size(I10) < Size(I0)/2. Теперь снова применим процедуру округления к I10, чтобы получить I2, и решим задачу LP для I2. И вновь это решение имеет не более Size(I10)/2 < Size(I0)/4 дробно заданных переменных, а OPT(I10) < OPT(I2) + c и LP(I2) < LP(I10). Вышеописанный процесс повторяется на протяжении нескольких шагов. На каждом шаге размер остаточного экземпляра уменьшается не менее чем в два раза, а количество контейнеров, необходимых для упаковки 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