Упаковка в контейнеры с высокой кратностью

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

Определение проблемы

Входными данными для задачи являются положительные целые числа:

d – количество различных размеров (также называемое размерностью задачи);
Б – емкость бункера.
s ₁ , ..., s _d - размеры. Вектор размеров обозначается s .
n ₁ , ..., n _d - кратности; n _i — количество элементов размера s _i . Вектор кратностей обозначается n .
- n обозначает общее количество элементов, то есть n = n ₁ +...+ n _d .
- V обозначает наибольшее целое число, встречающееся в описании задачи, то есть V = max( s ₁ , ..., s _d , n ₁ , ..., n _d , B)

На выходе получается упаковка — распределение предметов по ячейкам так, чтобы общий размер предметов в каждой ячейке был не более B , при этом количество ячеек было как можно меньшим.

Пример : предположим, 2 , s1 _s2 =30, 40 ₌ , n1 _n2 = = _d =5, B =120. Итак, имеется n =10 предметов с размерами: 30,30,30,30,30,40,40,40,40,40. Тогда возможная упаковка: {30,30,30,30}, {40,40,40}, {30,40,40}, при которой используются 3 контейнера.

Конфигурации

Конфигурация — это набор элементов, которые могут поместиться в одну корзину. Его можно представить вектором из d целых чисел, обозначающих кратности разных размеров в конфигурации. Формально, для каждой конфигурации c мы определяем целочисленный вектор a _c = a _c,1 , ..., a _c,d такой, что a _c ⩽ n и a _c · s ⩽ B.

В приведенном выше примере одна из конфигураций — c = {30,40,40}, поскольку 1*30+2*40 ≤ 120. Соответствующий ей вектор — = _c (1,2). Другие векторы конфигурации: (4,0), (3,0), (2,0), (2,1), (1,0), (1,1), (1,2), (0,1 ), (0,2), (0,3). Если бы у нас было только три элемента размера 3, мы бы не смогли использовать конфигурацию (4,0).

Можно представить задачу с помощью линейной программы конфигурации : для каждой конфигурации c существует переменная x _c , обозначающая количество ячеек, в которых c используется . Общее количество используемых интервалов представляет собой просто сумму x _c по всем конфигурациям, обозначаемую 1 · x . Общее количество использованных предметов каждого размера представляет собой сумму векторов a _c · x _c по всем конфигурациям c. Тогда задача состоит в том, чтобы минимизировать 1 · x так, чтобы сумма a _c · x _c по всем конфигурациям c была не меньше n , чтобы все элементы были упакованы.

Алгоритмы

Основные алгоритмы

Предположим сначала, что все элементы большие, то есть каждый s _i равен не менее e·B для некоторой дроби e >0. Тогда общее количество элементов в каждом контейнере не превышает 1/ e , поэтому общее количество конфигураций не превышает d. ^{1/ и}. Каждая конфигурация появляется не более n раз. Поэтому существует максимум $n^{d^{1/e}}$ комбинации для проверки. Для каждой комбинации нам нужно проверить d ограничений (по одному для каждого размера), поэтому время выполнения равно $d\cdot n^{d^{1/e}}$ , который является полиномиальным по n, когда d, e постоянны. ^[1]

Основная проблема этого алгоритма (помимо того факта, что он работает только тогда, когда элементы большие) заключается в том, что время его выполнения полиномиально от n , но длина входных данных (в двоичном представлении) линейна от log( V ), что порядка log( n ).

Полином времени выполнения входного размера

Филип и Агнес ^[2] представил алгоритм, который находит решение с не более чем OPT+ d -2 интервалами за время O(poly(log V )). В частности, для d =2 разных размеров их алгоритм находит оптимальное решение за время O(log V ).

Гоеманс и Ротвосс ^[3]^[4] представил алгоритм для любого фиксированного d , который находит оптимальное решение, когда все числа заданы в двоичном кодировании. Их алгоритм решает следующую задачу: по двум d -мерным многогранникам P и Q найти минимальное количество целых точек в P, лежит в Q. сумма которых Их алгоритм работает во времени $(\log V)^{2^{O(d)}}$ . Их алгоритм можно адаптировать к другим задачам, таким как планирование идентичных машин и планирование несвязанных машин с различными ограничениями.

Округление общего экземпляра до экземпляра с высокой кратностью

Несколько алгоритмов аппроксимации общей задачи упаковки контейнеров используют следующую схему:

Разделите элементы на «маленькие» (меньше eB для некоторой доли e в (0,1)) и «большие» (по крайней мере eB ).
Сначала разберитесь с крупными предметами:
- Округлите размеры предметов так, чтобы количество разных размеров было не более чем некоторой константой d.
- Решите полученную задачу большой кратности.
Распределяйте мелкие предметы жадно, например, с помощью упаковки в следующую корзину . Если новые контейнеры не созданы, то все готово. Если создаются новые контейнеры, это означает, что все контейнеры (кроме, возможно, последнего) заполнены как минимум до (1- e ) B . Следовательно, количество интервалов не превышает OPT/(1- e )+1 ≤ (1+2e ) OPT+1.

Алгоритмы различаются по способу обхода экземпляра.

Линейное округление

Люкер и де-ла-Вега и ^[5] изобрел идею адаптивного округления входных данных . Упорядочите предметы по размеру и сгруппируйте их в 1/ e. ² группы мощности ne ². В каждой группе округлите размеры в большую сторону до максимального размера в группе. Теперь есть только d =1/ e ² разные размеры. Решение округленного экземпляра возможно и для исходного экземпляра, но количество интервалов может быть больше, чем необходимо. Чтобы количественно оценить потери, рассмотрим экземпляр, округленный до максимального размера в предыдущей группе (первая группа округляется до 0). Округленный экземпляр D почти равен округленному экземпляру U , за исключением того, что в D есть некоторые новые ² нули, а в U есть некоторые пе ² вместо этого большие предметы; их размер не превышает B. но Следовательно, для U требуется не более ne ² больше бункеров, чем D . Поскольку D требует меньше интервалов, чем оптимально, мы получаем, что Bins( U ) ≤ OPT + ne ², то есть у нас есть аддитивная ошибка, которую можно сделать сколь угодно маленькой, выбрав e .

Если все элементы большие (размером не менее eB ), то каждая ячейка в OPT содержит не более 1/ e предметов (размером не менее eB ), поэтому OPT должен быть не менее en . Следовательно, Bins( U ) ≤ (1+ e )OPT. Обработав мелкие предметы, мы получаем максимум $(1+2e)\mathrm {OPT} +1$ .

Геометрическое округление

Кармаркар и Карп ^[6] представляют более эффективный метод округления, который они называют геометрическим округлением (в отличие от линейного округления Де-ла-Веги и Люкера). Основываясь на этих нововведениях, они представляют алгоритм с полиномом времени выполнения в $n$ и $1/\varepsilon$ . Их алгоритм находит решение размером не более $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))$ .

Улучшения

Позднее этот метод был усовершенствован несколькими авторами:

Ротвосс ^[7] представил алгоритм, который генерирует решение размером не более $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ .

Хоберг и Ротвосс ^[8] улучшен этот алгоритм, чтобы генерировать решение с максимальным размером $\mathrm {OPT} +O(\log(\mathrm {OPT} ))$ . Алгоритм рандомизирован, а время его работы полиномиально от общего количества элементов.

См. также

Проблема сокращения запасов - аналогична упаковке большого количества контейнеров, но цель состоит в том, чтобы минимизировать общий объем неиспользуемого пространства в каждом контейнере, а не количество контейнеров. Более того, в некоторых вариантах количество предметов каждого размера не фиксировано, а может перемещаться между некоторыми заданными нижними и верхними границами.

Ссылки

^ Клэр Матье. «Алгоритмы аппроксимации. Часть I, неделя 3: упаковка контейнеров» . Курсера .
^ Филиппи, Карло; Агнетис, Алессандро (1 сентября 2005 г.). «Асимптотически точный алгоритм решения задачи упаковки контейнеров с большой кратностью» . Математическое программирование . 104 (1): 21–37. дои : 10.1007/s10107-004-0567-y . ISSN 1436-4646 . S2CID 15140484 .
^ Гоеманс, Мишель X.; Ротвос, Томас (18 декабря 2013 г.), «Полиномиальность упаковки контейнеров с постоянным количеством типов предметов» , Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2014 г. , Труды Общества промышленной и прикладной математики, стр. 830–839, doi : 10.1137/1.9781611973402.61 , hdl : 1721.1/92865 , ISBN 978-1-61197-338-9 , S2CID 14006427 , получено 17 августа 2021 г.
^ Гоеманс, Мишель X.; Ротвосс, Томас (07.11.2020). «Полиномиальность упаковки контейнеров с постоянным количеством типов предметов» . Журнал АКМ . 67 (6): 38:1–38:21. дои : 10.1145/3421750 . hdl : 1721.1/92865 . ISSN 0004-5411 . S2CID 14006427 .
^ Фернандес де ла Вега, В.; Люкер, Г.С. (1981). «Упаковку контейнеров можно решить за 1 + ε за линейное время». Комбинаторика . 1 (4): 349–355. дои : 10.1007/BF02579456 . ISSN 1439-6912 . S2CID 10519631 .
^ Кармаркар, Нарендра; Карп, Ричард М. (ноябрь 1982 г.). «Эффективная аппроксимационная схема одномерной задачи упаковки контейнеров» . 23-й ежегодный симпозиум по основам информатики (SFCS 1982) : 312–320. дои : 10.1109/SFCS.1982.61 . S2CID 18583908 .
^ Ротвосс, Т. (1 октября 2013 г.). «Аппроксимация упаковки ячеек в ячейки O(log OPT · Log Log OPT)» . 54-й ежегодный симпозиум IEEE по основам информатики , 2013 г. стр. 20–29. arXiv : 1301.4010 . дои : 10.1109/FOCS.2013.11 . ISBN 978-0-7695-5135-7 . S2CID 15905063 .
^ Хоберг, Ребекка; Ротвосс, Томас (01 января 2017 г.), «Логарифмический аддитивный разрыв целостности для упаковки контейнеров», Труды ежегодного симпозиума ACM-SIAM 2017 г. по дискретным алгоритмам , Труды Общества промышленной и прикладной математики, стр. 2616–2625, arXiv : 1503.08796 , doi : 10.1137/1.9781611974782.172 , ISBN 978-1-61197-478-2 , S2CID 1647463

[:2-1] Клэр Матье. «Алгоритмы аппроксимации. Часть I, неделя 3: упаковка контейнеров» . Курсера .

[2] Филиппи, Карло; Агнетис, Алессандро (1 сентября 2005 г.). «Асимптотически точный алгоритм решения задачи упаковки контейнеров с большой кратностью» . Математическое программирование . 104 (1): 21–37. дои : 10.1007/s10107-004-0567-y . ISSN 1436-4646 . S2CID 15140484 .

[3] Гоеманс, Мишель X.; Ротвос, Томас (18 декабря 2013 г.), «Полиномиальность упаковки контейнеров с постоянным количеством типов предметов» , Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2014 г. , Труды Общества промышленной и прикладной математики, стр. 830–839, doi : 10.1137/1.9781611973402.61 , hdl : 1721.1/92865 , ISBN 978-1-61197-338-9 , S2CID 14006427 , получено 17 августа 2021 г.

[4] Гоеманс, Мишель X.; Ротвосс, Томас (07.11.2020). «Полиномиальность упаковки контейнеров с постоянным количеством типов предметов» . Журнал АКМ . 67 (6): 38:1–38:21. дои : 10.1145/3421750 . hdl : 1721.1/92865 . ISSN 0004-5411 . S2CID 14006427 .

[5] Фернандес де ла Вега, В.; Люкер, Г.С. (1981). «Упаковку контейнеров можно решить за 1 + ε за линейное время». Комбинаторика . 1 (4): 349–355. дои : 10.1007/BF02579456 . ISSN 1439-6912 . S2CID 10519631 .

[:12-6] Кармаркар, Нарендра; Карп, Ричард М. (ноябрь 1982 г.). «Эффективная аппроксимационная схема одномерной задачи упаковки контейнеров» . 23-й ежегодный симпозиум по основам информатики (SFCS 1982) : 312–320. дои : 10.1109/SFCS.1982.61 . S2CID 18583908 .

[:22-7] Ротвосс, Т. (1 октября 2013 г.). «Аппроксимация упаковки ячеек в ячейки O(log OPT · Log Log OPT)» . 54-й ежегодный симпозиум IEEE по основам информатики , 2013 г. стр. 20–29. arXiv : 1301.4010 . дои : 10.1109/FOCS.2013.11 . ISBN 978-0-7695-5135-7 . S2CID 15905063 .

[:3-8] Хоберг, Ребекка; Ротвосс, Томас (01 января 2017 г.), «Логарифмический аддитивный разрыв целостности для упаковки контейнеров», Труды ежегодного симпозиума ACM-SIAM 2017 г. по дискретным алгоритмам , Труды Общества промышленной и прикладной математики, стр. 2616–2625, arXiv : 1503.08796 , doi : 10.1137/1.9781611974782.172 , ISBN 978-1-61197-478-2 , S2CID 1647463

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]