Проблема с упаковкой контейнера

Не путать со сбором мусора .

ведра Проблема с упаковкой мусорного Это задача оптимизации , в которой предметы разного размера должны быть упакованы в конечное число контейнеров или контейнеров, каждый из которых имеет фиксированную заданную вместимость, таким образом, чтобы минимизировать количество используемых контейнеров. Проблема имеет множество применений, таких как заполнение контейнеров, загрузка грузовиков с ограничениями по весу, создание резервных копий файлов на носителе, разделение сетевого префикса на несколько подсетей, и картирование технологий при FPGA проектировании полупроводниковых чипов .

В вычислительном отношении задача является NP-сложной , а соответствующая задача решения , позволяющая решить, могут ли элементы поместиться в заданное количество ячеек, является NP-полной . Несмотря на сложность наихудшего случая, оптимальные решения для очень больших случаев задачи могут быть получены с помощью сложных алгоритмов. Кроме того, множество алгоритмов аппроксимации существует . Например, алгоритм первого соответствия обеспечивает быстрое, но зачастую неоптимальное решение, предполагающее помещение каждого элемента в первую корзину, в которую он поместится. Для этого требуется время Θ ( n log n ), где n — количество упаковываемых предметов. Алгоритм можно сделать намного более эффективным, если сначала отсортировать список элементов в порядке убывания (иногда известный как алгоритм убывания по первому совпадению), хотя это все равно не гарантирует оптимальное решение, а для более длинных списков может увеличиться время работы. алгоритм. Однако известно, что всегда существует хотя бы один порядок элементов, который позволяет методом первого подбора получить оптимальное решение.

Существует множество вариантов этой задачи, например двумерная упаковка, линейная упаковка, упаковка по весу, упаковка по стоимости и т. д. Проблему упаковки корзин также можно рассматривать как частный случай проблемы раскроя запасов . Когда количество корзин ограничено 1 и каждый предмет характеризуется как объемом, так и стоимостью, проблема максимизации ценности предметов, которые могут поместиться в корзину, известна как задача о рюкзаке .

На практике встречается вариант упаковки в корзину, когда предметы могут разделять пространство при упаковке в корзину. В частности, набор предметов в упаковке может занимать меньше места, чем сумма их индивидуальных размеров. Этот вариант известен как упаковка VM. поскольку когда виртуальные машины (ВМ) упакованы на сервер, их общая потребность в памяти может уменьшиться из-за страниц, совместно используемых ВМ, которые необходимо сохранить только один раз. Если предметы могут распределять пространство произвольным образом, проблему упаковки в мусорные корзины трудно даже приблизительно представить. Однако если совместное использование пространства вписывается в иерархию, как в случае совместного использования памяти в виртуальных машинах, проблема упаковки ячеек может быть эффективно решена.

Еще одним вариантом упаковки контейнеров, представляющим практический интерес, является так называемая онлайн- упаковка контейнеров. Здесь предметы различного объема должны поступать последовательно, и ЛПР должен решить, следует ли выбрать и упаковать наблюдаемый в данный момент предмет или пропустить его. Каждое решение не подлежит отзыву. Напротив, автономная упаковка в корзину позволяет переставлять предметы в надежде добиться лучшей упаковки после прибытия дополнительных товаров. Это, конечно, требует дополнительного места для хранения предметов, подлежащих перестановке.

Официальное заявление

В компьютерах и трудноразрешимости Гэри и Джонсон перечисляют проблему упаковки контейнеров в ссылке [SR1]. Вариант его решения они определяют следующим образом.

Пример: конечное множество $I$ предметов, размер $s(i)\in \mathbb {Z} ^{+}$ для каждого $i\in I$, положительное целое число емкость бункера $B$и положительное целое число $K$.

Вопрос: Есть ли раздел $I$ на непересекающиеся множества $I_{1},\dots ,I_{K}$ такая, что сумма размеров предметов в каждом $I_{j}$ является $B$ или меньше?

Отметим, что в литературе часто используются эквивалентные обозначения, где $B=1$ и $s(i)\in \mathbb {Q} \cap (0,1]$ для каждого $i\in I$. Кроме того, исследования больше всего интересуют варианты оптимизации, которые требуют минимально возможного значения $K$. Решение является оптимальным, если оно имеет минимальную $K$. $K$-значение оптимального решения для набора предметов $I$ обозначается $\mathrm {OPT} (I)$ или просто $\mathrm {OPT}$ если набор предметов ясен из контекста.

Возможная целочисленным линейным программированием формулировка задачи :

минимизировать $K=\sum _{j=1}^{n}y_{j}$
при условии	$K\geq 1,$
	$\sum _{i\in I}s(i)x_{ij}\leq By_{j},$	$\forall j\in \{1,\ldots ,n\}$
	$\sum _{j=1}^{n}x_{ij}=1,$	$\forall i\in I$
	$y_{j}\in \{0,1\},$	$\forall j\in \{1,\ldots ,n\}$
	$x_{ij}\in \{0,1\},$	$\forall i\in I\,\forall j\in \{1,\ldots ,n\}$

где $y_{j}=1$ если мусорное ведро $j$ используется и $x_{ij}=1$ если предмет $i$ помещается в корзину $j$.

Твердость упаковки контейнера

Задача упаковки контейнеров является строго NP-полной . Это можно доказать, сведя сильно NP-полную задачу трех разделов к упаковке контейнеров.

Более того, не может быть алгоритма аппроксимации с абсолютным коэффициентом аппроксимации меньшим, чем ${\tfrac {3}{2}}$ пока не ${\mathsf {P}}={\mathsf {NP}}$. Это можно доказать, редукционируя к задаче о разделах : учитывая экземпляр раздела, где сумма всех входных чисел равна $2T$, создайте экземпляр упаковки контейнеров, в котором размер контейнера равен T . Если существует равное разделение входных данных, то для оптимальной упаковки требуется 2 контейнера; следовательно, каждый алгоритм с коэффициентом аппроксимации меньшим, чем ⁠ 3/2 . ⁠ ячейки должно возвращать менее 3 ячеек, что должно составлять 2 Напротив, если нет равного разделения входов, то для оптимальной упаковки требуется как минимум 3 контейнера.

С другой стороны, упаковка контейнеров разрешима за псевдополиномиальное время для любого фиксированного числа контейнеров K и разрешима за полиномиальное время для любой фиксированной емкости контейнера B .

Алгоритмы аппроксимации упаковки контейнеров

Для измерения производительности алгоритма аппроксимации в литературе рассматриваются два коэффициента аппроксимации. Для заданного списка элементов $L$ число $A(L)$ обозначает количество ячеек, используемых при алгоритме $A$ применяется к списку $L$, пока $\mathrm {OPT} (L)$ обозначает оптимальное число для этого списка. Абсолютный наихудший коэффициент производительности $R_{A}$ для алгоритма $A$ определяется как

$R_{A}\equiv \inf\{r\geq 1:A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L\}.$

С другой стороны, асимптотическое отношение наихудшего случая $R_{A}^{\infty }$ определяется как

$R_{A}^{\infty }\equiv \inf\{r\geq 1:\exists N>0,A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L{\text{ with }}\mathrm {OPT} (L)\geq N\}.$

Эквивалентно, $R_{A}^{\infty }$ — наименьшее число такое, что существует некоторая константа K, такая что для всех списков L:

$A(L)\leq R_{A}^{\infty }\cdot \mathrm {OPT} (L)+K$.

Кроме того, можно ограничить списки теми, в которых все элементы имеют размер не более $\alpha$. Для таких списков коэффициенты производительности ограниченного размера обозначаются как $R_{A}({\text{size}}\leq \alpha )$ и $R_{A}^{\infty }({\text{size}}\leq \alpha )$.

Алгоритмы аппроксимации упаковки контейнеров можно разделить на две категории:

1. Онлайн-эвристика, которая рассматривает элементы в заданном порядке и помещает их один за другим в корзины. Эти эвристики также применимы к автономной версии этой задачи.
2. Автономная эвристика, которая изменяет заданный список элементов, например, сортируя элементы по размеру. Эти алгоритмы больше не применимы к онлайн-варианту этой задачи. Однако они имеют улучшенную гарантию аппроксимации, сохраняя при этом преимущество своей небольшой временной сложности. Подкатегория автономных эвристик — это схемы асимптотической аппроксимации. Эти алгоритмы имеют гарантию аппроксимации вида $(1+\varepsilon )\mathrm {OPT} (L)+C$ для некоторой константы, которая может зависеть от $1/\varepsilon$. Для сколь угодно большого $\mathrm {OPT} (L)$ эти алгоритмы подбираются сколь угодно близко к $\mathrm {OPT} (L)$. Однако за это приходится платить (резко) увеличением временной сложности по сравнению с эвристическими подходами.

Онлайн-эвристика

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

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

Существует множество простых алгоритмов, использующих следующую общую схему:

• Для каждого элемента входного списка:
  1. Если предмет помещается в одну из открытых в данный момент ячеек, поместите его в одну из этих ячеек;
  2. В противном случае откройте новую корзину и поместите в нее новый предмет.

Алгоритмы различаются критерием, по которому они выбирают открытую корзину для нового товара на шаге 1 (дополнительную информацию см. на связанных страницах):

• Функция Next Fit (NF) всегда оставляет одну открытую корзину. Когда новый товар в него не помещается, он закрывает текущую корзину и открывает новую корзину. Его преимущество состоит в том, что это алгоритм с ограниченным пространством, поскольку ему нужно хранить в памяти только один открытый интервал. Его недостатком является то, что коэффициент асимптотической аппроксимации равен 2. В частности, $NF(L)\leq 2\cdot \mathrm {OPT} (L)-1$, и для каждого $N\in \mathbb {N}$ существует список L такой, что $\mathrm {OPT} (L)=N$ и $NF(L)=2\cdot \mathrm {OPT} (L)-2$. Его коэффициент асимптотической аппроксимации можно несколько улучшить в зависимости от размеров элемента: $R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2$ для всех $\alpha \geq 1/2$ и $R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )$ для всех $\alpha \leq 1/2$. Для каждого алгоритма A , который является алгоритмом AnyFit, справедливо следующее соотношение: $R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{NF}^{\infty }({\text{size}}\leq \alpha )$.
• Next-k-Fit (NkF) — это вариант Next-Fit, но вместо того, чтобы оставлять открытой только одну ячейку, алгоритм оставляет открытыми последние k ячеек и выбирает первую ячейку, в которую помещается элемент. Поэтому его называют алгоритмом с k-ограниченным пространством . Для $k\geq 2$ NkF дает результаты, которые улучшаются по сравнению с результатами NF, однако увеличение k до постоянных значений, превышающих 2, не приводит к дальнейшему улучшению алгоритма в его худшем случае. Если алгоритм A является алгоритмом ПочтиAnyFit и $m=\lfloor 1/\alpha \rfloor \geq 2$ затем $R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{size}}\leq \alpha )=1+1/m$.
• Функция First-Fit (FF) сохраняет все контейнеры открытыми в том порядке, в котором они были открыты. Он пытается поместить каждый новый элемент в первую корзину, в которую он помещается. Его коэффициент аппроксимации равен $FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$, и существует семейство входных списков L, для которого $FF(L)$ соответствует этой границе.
• Best-Fit (BF) также оставляет все контейнеры открытыми, но пытается поместить каждый новый предмет в контейнер с максимальной загрузкой, в которую он помещается. Его коэффициент аппроксимации идентичен коэффициенту FF, то есть: $BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$, и существует семейство входных списков L, для которого $BF(L)$ соответствует этой границе.
• Worst-Fit (WF) пытается поместить каждый новый предмет в корзину с минимальной загрузкой. Он может вести себя так же плохо, как Next-Fit, и попадет в список наихудших для этого случаев. $NF(L)=2\cdot \mathrm {OPT} (L)-2$. Кроме того, он утверждает, что $R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )$. Поскольку WF является алгоритмом AnyFit, существует алгоритм AnyFit такой, что $R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )$.
• Функция «Почти наихудшее соответствие» (AWF) пытается поместить каждый новый товар во вторую по величине пустую открытую корзину (или самую пустую корзину, если таких корзин две). Если не подходит, пробует самый пустой. Он имеет асимптотическое отношение наихудшего случая ${\tfrac {17}{10}}$.

Чтобы обобщить эти результаты, Джонсон ввел два класса онлайн-эвристик, называемых алгоритмом любого соответствия и алгоритмом почти любого соответствия :

• В алгоритме AnyFit (AF) , если текущие непустые ячейки — это B ₁ ,..., B _j , то текущий элемент не будет упакован в B _{j +1,} если только он не помещается ни в один из B ₁ ,.. ., Б _ж . Алгоритмы FF, WF, BF и AWF удовлетворяют этому условию. Джонсон доказал, что для любого алгоритма AnyFit A и любого $\alpha$:

  $R_{FF}^{\infty }(\alpha )\leq R_{A}^{\infty }(\alpha )\leq R_{WF}^{\infty }(\alpha )$.

• В алгоритме ПочтиAnyFit (AAF) , если текущие непустые контейнеры — это B ₁ ,..., B _j , и из этих контейнеров B _k — уникальный контейнер с наименьшей загрузкой, то текущий элемент не будет упакован в B. _k , если только он не помещается ни в одну из ячеек слева от него. Алгоритмы FF, BF и AWF удовлетворяют этому условию, а WF — нет. Джонсон доказал, что для любого алгоритма AAF A и любого α :

  $R_{A}^{\infty }(\alpha )=R_{FF}^{\infty }(\alpha )$ В частности: $R_{A}^{\infty }=1.7$.

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

Лучшие коэффициенты аппроксимации возможны при использовании эвристики, отличной от AnyFit. Эти эвристики обычно содержат несколько классов открытых ячеек, посвященных предметам разных размеров (дополнительную информацию см. на связанных страницах):

• Усовершенствованная упаковка контейнеров по принципу «первая установка» (RFF) делит размеры предметов на четыре диапазона: $\left({\frac {1}{2}},1\right]$, $\left({\frac {2}{5}},{\frac {1}{2}}\right]$, $\left({\frac {1}{3}},{\frac {2}{5}}\right]$, и $\left(0,{\frac {1}{3}}\right]$. Аналогичным образом контейнеры делятся на четыре класса. Следующий пункт $i\in L$ сначала присваивается соответствующему классу. Внутри этого класса он назначается ячейке с помощью first-fit . Обратите внимание, что этот алгоритм не является алгоритмом Any-Fit, поскольку он может открыть новую корзину, несмотря на то, что текущий элемент помещается в открытую корзину. Этот алгоритм был впервые представлен Эндрю Чи-Чи Яо, который доказал, что он имеет гарантию аппроксимации $RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5$ и представил семейство списков $L_{k}$ с $RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3$ для $\mathrm {OPT} (L)=6k+1$.
• Гармоника-k разбивает интервал размеров $(0,1]$ основанный на Гармонической прогрессии в $k-1$ куски $I_{j}:=\left({\frac {1}{j+1}},{\frac {1}{j}}\right]$ для $1\leq j<k$ и $I_{k}:=\left(0,{\frac {1}{k}}\right]$ такой, что $\bigcup _{j=1}^{k}I_{j}=(0,1]$. Этот алгоритм был впервые описан Ли и Ли. Имеет временную сложность ${\mathcal {O}}(|L|\log(|L|))$ и на каждом шаге имеется не более k открытых ячеек, которые потенциально можно использовать для размещения предметов, т. е. это алгоритм с k -ограниченным пространством. Для $k\rightarrow \infty$, его коэффициент аппроксимации удовлетворяет $R_{Hk}^{\infty }\approx 1.6910$, и оно асимптотически тесно.
• Refined-harmonic сочетает в себе идеи из Harmonic-k с идеями из Refined-First-Fit . Он помещает элементы размером больше, чем ${\tfrac {1}{3}}$ аналогично методу Refined-First-Fit, тогда как более мелкие элементы размещаются с использованием Harmonic-k. Идея этой стратегии заключается в том, чтобы уменьшить количество огромных отходов в контейнерах, содержащих куски размером чуть больше ${\tfrac {1}{2}}$. Этот алгоритм был впервые описан Ли и Ли. Они доказали, что для $k=20$ он утверждает, что $R_{RH}^{\infty }\leq 373/228$.

Общие нижние оценки для онлайн-алгоритмов

Их доказал в 1980 году, что не может быть онлайн-алгоритма с асимптотическим коэффициентом конкуренции меньшим, чем ${\tfrac {3}{2}}$. Коричневый и Лян улучшил эту границу до 1,536 35 . Впоследствии эта граница была улучшена до 1,540 14 . Влитом В 2012 году эту нижнюю границу снова улучшили Бекеши и Галамбос. к ${\tfrac {248}{161}}\approx 1.54037$.

Сравнительная таблица

Алгоритм	Гарантия аппроксимации	Список худшего случая $L$	Временная сложность
Следующий вариант (NF)	$NF(L)\leq 2\cdot \mathrm {OPT} (L)-1$	$NF(L)=2\cdot \mathrm {OPT} (L)-2$	${\mathcal {O}}(|L|)$
Первая установка (FF)	$FF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor$	$FF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor$	${\mathcal {O}}(|L|\log(|L|))$
Наиболее подходящий (BF)	$BF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor$	$BF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor$	${\mathcal {O}}(|L|\log(|L|))$
Наихудший вариант (WF)	$WF(L)\leq 2\cdot \mathrm {OPT} (L)-1$	$WF(L)=2\cdot \mathrm {OPT} (L)-2$	${\mathcal {O}}(|L|\log(|L|))$
Почти наихудшее соответствие (AWF)	$R_{AWF}^{\infty }\leq 17/10$	$R_{AWF}^{\infty }=17/10$	${\mathcal {O}}(|L|\log(|L|))$
«Уточненная первая установка» (RFF)	$RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5$	$RFF(L)=(5/3)\mathrm {OPT} (L)+1/3$ (для $\mathrm {OPT} (L)=6k+1$)	${\mathcal {O}}(|L|\log(|L|))$
Гармоника-к (Hk)	$R_{Hk}^{\infty }\leq 1.69103$ для $k\rightarrow \infty$	$R_{Hk}^{\infty }\geq 1.69103$	${\mathcal {O}}(|L|\log(|L|)$
Утонченная гармоника (RH)	$R_{RH}^{\infty }\leq 373/228\approx 1.63597$		${\mathcal {O}}(|L|)$
Модифицированная гармоника (MH)	$R_{MH}^{\infty }\leq 538/33\approx 1.61562$
Модифицированная гармоника 2 (MH2)	$R_{MH2}^{\infty }\leq 239091/148304\approx 1.61217$
Гармоника + 1 (H+1)		$R_{H+1}^{\infty }\geq 1.59217$
Гармоника++ (H++)	$R_{H++}^{\infty }\leq 1.58889$	$R_{H++}^{\infty }\geq 1.58333$

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

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

Мультипликативное приближение

Самый простой метод, используемый в схемах автономной аппроксимации, следующий:

• Упорядочение входного списка по убыванию размера;
• Запустите онлайн-алгоритм в упорядоченном списке.

Джонсон доказал, что любая схема AnyFit A, которая работает со списком, упорядоченным по убыванию размера, имеет асимптотический коэффициент аппроксимации

$1.22\approx {\frac {11}{9}}\leq R_{A}^{\infty }\leq {\frac {5}{4}}=1.25$.

Некоторые методы этого семейства (дополнительную информацию см. на связанных страницах):

• Функция First-Fit-Dereasing (FFD) упорядочивает элементы по убыванию размера, а затем вызывает First-Fit. Его коэффициент аппроксимации равен $FFD(I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}$, а это туго.
• Функция Next-Fit-Dereasing (NFD) упорядочивает элементы по убыванию размера, а затем вызывает Next-Fit . Его приблизительное соотношение в худшем случае чуть меньше 1,7. Это также было проанализировано вероятностно. Next-Fit упаковывает список и его инверсию в одинаковое количество ячеек. Таким образом, функция Next-Fit-Increasing имеет ту же производительность, что и Next-Fit-Decreasing.
• Модифицированный метод уменьшения первого соответствия (MFFD) , улучшает FFD для предметов размером более половины корзины за счет разделения предметов по размеру на четыре размера: большой, средний, маленький и крошечный, что соответствует предметам размером > 1/2 корзины, > 1/3 корзины, > 1/6 корзины. мусорное ведро и более мелкие предметы соответственно. Его гарантия аппроксимации равна $MFFD(I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1$.

Фернандес де ла Вега и Люкер представила PTAS для упаковки в мусорные контейнеры. Для каждого $\varepsilon >0$, их алгоритм находит решение размером не более $(1+\varepsilon )\mathrm {OPT} +1$ и бежит во времени ${\mathcal {O}}(n\log(1/\varepsilon ))+{\mathcal {O}}_{\varepsilon }(1)$, где ${\mathcal {O}}_{\varepsilon }(1)$ обозначает функцию, зависящую только от $1/\varepsilon$. Для этого алгоритма придумали метод адаптивного округления входных данных : входные числа группируются и округляются до значения максимума в каждой группе. В результате получается экземпляр с небольшим количеством разных размеров, который можно точно решить с помощью линейной программы конфигурации .

Аддитивное приближение

находит Алгоритм упаковки контейнеров Кармаркара-Карпа решение с размером не более $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))$и работает за полиномиальное от n время (многочлен имеет высокую степень, не менее 8).

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

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

Сравнительная таблица

Алгоритм	Гарантия аппроксимации	Худший случай
Уменьшение при первом приближении (FFD)	$\mathrm {FFD} (I)\leq {\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}$	$\mathrm {FFD} (I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}$
Модифицированное уменьшение первого соответствия (MFFD)	$\mathrm {MFFD} (I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1$	$R_{\mathrm {MFFD} }^{\infty }\geq {\frac {71}{60}}$
Кармаркар и Карп	$\mathrm {KK} (I)\leq \mathrm {OPT} (I)+O(\log ^{2}{\mathrm {OPT} (I)})$
Ротвосс	$\mathrm {HB} (I)\leq \mathrm {OPT} (I)+O(\log {\mathrm {OPT} (I)}\log \log {\mathrm {OPT} (I)})$
Хоберг и Ротвосс	$\mathrm {HB} (I)\leq \mathrm {OPT} (I)+O(\log {\mathrm {OPT} (I)})$

Точные алгоритмы

Мартелло и Тот разработал точный алгоритм для одномерной задачи упаковки контейнеров, названный MTP. Более быстрая альтернатива - алгоритм Bin Completion, предложенный Корфом в 2002 году. и позже улучшилось.

Дальнейшее улучшение было представлено Шрайбером и Корфом в 2013 году. Показано, что новый алгоритм Improved Bin Completion на пять порядков быстрее, чем Bin Completion, при решении нетривиальных задач со 100 элементами и превосходит алгоритм BCP (ветвь, разрезание и цена), разработанный Беловым и Шейтауэром на задачи, для которых оптимальным решением является менее 20 контейнеров. Какой алгоритм работает лучше всего, зависит от свойств задачи, таких как количество элементов, оптимальное количество ячеек, неиспользуемое пространство в оптимальном решении и точность значений.

Небольшое количество разных размеров

Особым случаем упаковки в контейнеры является ситуация, когда имеется небольшое количество d предметов разных размеров. Может быть много разных предметов каждого размера. Этот случай также называется упаковкой контейнеров с высокой кратностью , и он допускает более эффективные алгоритмы, чем общая задача.

Бин-упаковка с фрагментацией

Упаковка в корзину с фрагментацией или упаковка в корзину для фрагментируемых предметов — это вариант задачи об упаковке в корзину, в которой допускается разбивать предметы на части и помещать каждую часть отдельно в отдельный контейнер. Разбиение элементов на части может позволить улучшить общую производительность, например, свести к минимуму общее количество корзин. Более того, вычислительная задача поиска оптимального расписания может стать проще, поскольку некоторые переменные оптимизации становятся непрерывными. С другой стороны, разбирать предметы на части может оказаться дорогостоящим. Эту проблему впервые предложили Мандал, Чакрабари и Гхош.

Варианты

Проблема имеет два основных варианта.

1. В первом варианте, называемом бин-упаковкой с фрагментацией по увеличению размера ( BP-SIF ), каждый предмет может быть фрагментирован; служебные единицы добавляются к размеру каждого фрагмента.
2. Во втором варианте, называемом бин-упаковкой с фрагментацией с сохранением размера ( BP-SPF ), каждый предмет имеет размер и стоимость; фрагментация предмета увеличивает его стоимость, но не меняет его размер.

Вычислительная сложность

Мандал, Чакрабари и Гхош доказал, что BP-SPF является NP-жестким .

Менакерман и Ром показали, что BP-SIF и BP-SPF являются сильно NP-жесткими . Несмотря на сложность, они представляют несколько алгоритмов и исследуют их работу. используются классические алгоритмы упаковки контейнеров, такие как уменьшение следующего и первого соответствия В их алгоритмах в качестве основы для своих алгоритмов .

Бертацци, Голден и Ван представил вариант BP-SIF с $1-x$ Правило разделения: элемент можно разделить только одним способом в зависимости от его размера. Это полезно для решения задачи маршрутизации транспортных средств , например, . В своей статье они приводят оценку производительности варианта для наихудшего случая.

Шахнай, Тамир и Ехезкели разработаны аппроксимационные схемы БП-СИФ и БП-СПФ; двойственный PTAS (PTAS для двойственной версии задачи), асимптотический PTAS, называемый APTAS, и двойственный асимптотический FPTAS, называемый AFPTAS, для обеих версий.

Плантатор введён вариант БП-СПФ, в котором некоторые предметы конфликтуют, и запрещено упаковывать фрагменты конфликтных предметов в одну корзину. Они доказали, что и этот вариант NP-труден.

Кассацца и Чезелли введен вариант без затрат и накладных расходов, а количество бункеров фиксировано. Однако количество фрагментаций должно быть сведено к минимуму. Они представляют алгоритмы математического программирования как для точных, так и для приближенных решений.

Связанные проблемы

Задачу о дробном ранце со штрафами предложили Малагути, Моначи, Паронуцци и Пферши. Они разработали FPTAS и динамическую программу для решения этой проблемы, а также продемонстрировали обширное вычислительное исследование, сравнивающее производительность своих моделей. См. также: Дробное планирование заданий .

Производительность с делимыми размерами предметов

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

Ограничения мощности ячеек

Существует вариант упаковки контейнеров, в котором существуют ограничения на мощность контейнеров: каждый контейнер может содержать не более k элементов для некоторого фиксированного целого числа k .

• Краузе, Шен и Шветман Представим эту задачу как вариант оптимального планирования заданий : компьютер имеет несколько k процессоров. Существует несколько n заданий, которые занимают единицу времени (1), но имеют разные требования к памяти. Каждая единица времени считается отдельным интервалом. Цель состоит в том, чтобы использовать как можно меньше контейнеров (=единиц времени), гарантируя при этом, что в каждом контейнере выполняется не более k заданий. Они представляют несколько эвристических алгоритмов, которые находят решение не более чем за $2\mathrm {OPT}$ контейнеры.
• Келлерер и Пферши представить алгоритм во время выполнения $O(n^{2}\log {n})$, который находит решение с не более чем $\left\lceil {\frac {3}{2}}\mathrm {OPT} \right\rceil$ контейнеры. Их алгоритм выполняет двоичный поиск OPT. Для каждого искомого значения m он пытается упаковать предметы в 3 м /2. контейнеры размером

Неаддитивные функции

Существуют различные способы расширения модели упаковки контейнеров для более общих функций затрат и нагрузки:

• Анилий, Брамель и Симчи-Леви изучите ситуацию, в которой стоимость корзины является вогнутой функцией количества предметов в корзине. Целью является минимизация общей стоимости, а не количества контейнеров. Они показывают, что упаковка контейнеров с увеличением следующего соответствия достигает абсолютного коэффициента аппроксимации наихудшего случая не более 7/4 и асимптотического коэффициента наихудшего случая 1,691 для любой вогнутой и монотонной функции стоимости.
• Коэн, Келлер, Миррокни и Задимогаддам изучите обстановку, в которой размер предметов заранее не известен, но является случайной величиной . Это особенно распространено в средах облачных вычислений . Несмотря на то, что существует верхний предел объема ресурсов, необходимых определенному пользователю, большинство пользователей используют гораздо меньше емкости. Таким образом, облачный менеджер может много выиграть от небольшого превышения обязательств . Это приводит к варианту упаковки контейнеров со случайными ограничениями : вероятность того, что сумма размеров в каждом контейнере не превышает B, должна быть не меньше p , где p — фиксированная константа (стандартная упаковка контейнеров соответствует p = 1). Они показывают, что при мягких предположениях эта проблема эквивалентна задаче об упаковке субмодульной корзины , в которой «нагрузка» в каждой корзине равна не сумме предметов, а некоторой субмодульной функции . ее

Связанные проблемы

В задаче об упаковке контейнеров размер контейнеров фиксирован, а их количество можно увеличить (но оно должно быть как можно меньшим).

Напротив, в многостороннего разделения чисел задаче количество ячеек фиксировано, а их размер может быть увеличен. Цель состоит в том, чтобы найти раздел, в котором размеры ячеек будут как можно более равными (в варианте, называемом многопроцессорного планирования проблемой или проблемой минимального времени обработки , цель состоит в том, чтобы минимизировать размер наибольшего контейнера).

В задаче об обратной упаковке контейнеров : и количество корзин, и их размеры фиксированы, но размеры предметов можно изменить. Цель состоит в том, чтобы добиться минимального отклонения вектора размера предмета, чтобы все предметы можно было упаковать в заданное количество контейнеров.

В задаче об упаковке контейнера с максимальным количеством ресурсов : цель состоит в том, чтобы максимизировать количество используемых ячеек так, чтобы при некотором упорядочении ячеек ни один предмет из более поздней ячейки не помещался в более раннюю корзину. В двойной задаче количество корзин фиксировано, и цель состоит в том, чтобы минимизировать общее количество или общий размер предметов, помещенных в корзины, так, чтобы ни один оставшийся предмет не помещался в незаполненную корзину.

В задаче покрытия ячеек размер ячейки ограничен снизу : цель состоит в том, чтобы максимизировать количество используемых ячеек так, чтобы общий размер в каждой ячейке был не ниже заданного порога.

В задаче справедливого неделимого распределения обязанностей (вариант справедливого распределения элементов ) элементы представляют собой работу по дому, и есть разные люди, каждый из которых приписывает каждой работе разное значение сложности. Цель состоит в том, чтобы распределить для каждого человека набор обязанностей с верхней границей общего значения сложности (таким образом, каждый человек соответствует корзине). В этой задаче также используются многие методы упаковки в контейнеры.

В задаче гильотинной резки и предметы, и «корзины» представляют собой двумерные прямоугольники, а не одномерные числа, и предметы необходимо вырезать из корзины, используя сквозные разрезы.

В задаче об эгоистичной упаковке мусора каждый предмет — это игрок, который хочет минимизировать его стоимость.

Существует также вариант упаковки в контейнеры, при котором стоимость, которую следует минимизировать, представляет собой не количество контейнеров, а некоторую вогнутую функцию количества предметов в каждом контейнере.

Другие варианты — двухмерная упаковка в контейнер, трехмерная упаковка контейнера , контейнерная упаковка с доставкой ,

Ресурсы

• BPPLIB — библиотека опросов, кодов, тестов, генераторов, решателей и библиографии.