Задача про пакування в ємності

У теорії складності обчислень задача про розміщення в ємності (посудини) — NP-складна комбінаторна задача. Задача полягає в пакуванні об'єктів визначеної завідомо форми в скінченне число ємностей (також кажуть контейнерів) - теж завідомо відомої заздалегідь форми у такий спосіб, аби число використаних ємностей було найменшим, або кількість чи об'єм предметів (які розміщують) були якнайбільшими.

Різновиди та методи розв'язування задач упакування

Існує безліч різновидів цієї задачі (двомірне пакування, лінійне пакування, пакування на вагу, за вартістю тощо), що можуть застосовуватись у різних галузях, як власне у питанні якнайвигіднішого наповнення ємностей, навантаження напіввагона чи вантажівки з ваговим обмеженням; створення резервних копій на знімних носіях тощо.

Оскільки задача є NP-складною, то застосування точного перебірного алгоритму припустиме лише за невеликих розмірностей. Зазвичай для розв'язування цієї задачі використовують евристичні наближені поліноміальні алгоритми.

Спрощений підхід

Попри те, що математики зараз часто розв'язують нікому не потрібні задачі й уважають повсякденне життя за частинний випадок, не можна забувати про те, що найкращий розв'язок — це той, який нескладний, доступний для нематематиків та підходить для використання у побутових умовах (неможливо вираховувати годинами чи добами ідеальний варіант, коли, на приклад, рішення потрібно було прийняти «ще на тому тижні», комп'ютер старий і повільний, і як на те, ще й вимкнулось світло). Ледачий (жадібний) підхід, очевидно, є незамінним при розв'язуванні життєвих задач. Алгоритм обробляє речі в довільному порядку. Кожну річ він намагається помістити у першу-ліпшу посудину, куди вона здатна ввійти. Якщо такої не знайде, він дозволить відкрити нову посудину (в житті — сумку або вантажний вагон, або контейнер) і ставить його туди. Точно те саме роблять люди, коли переміщують досить значні речі: ще одну сумку, возик або валізу беруть лише в тому разі, коли неможливо помістити все у ті сумки, які у вас є. А ось вирішити, чи вам їхати поїздом, чи автобусом, чи машиною, а, може, вам взагалі треба відправляти вантаж товарним вагоном, цей алгоритм вам не допоможе, а якщо і допоможе, то неповністю: він не вміє визначити, чи помнуться речі у посудинах в такому положенні, чи можна (а якщо можна — то чи припустимо) їх стиснути або згорнути, наскільки легко їх буде дістати тощо. У цьому і полягає перевага людського мозку над комп'ютером.

Жадібний алгоритм забезпечує коефіцієнт наближення 2, тобто, кількість задіяних посудин не перевищить більш, ніж у два рази ту найвигіднішу їх кількість, яку комп'ютер буде вираховувати неприпустимо довго.

Задача про розміщення в одновимірні однакові ємності

Постановка задачі

Нехай дана множина ємностей розміру ${\displaystyle V}$ і множина ${\displaystyle n}$ предметів розмірів ${\displaystyle a_{1},\dots ,a_{n}}$. Необхідно знайти ціле число ємностей ${\displaystyle B}$ і розбиття множин ${\displaystyle \{1,\dots ,n\}}$ на ${\displaystyle B}$ таких підмножин ${\displaystyle S_{1}\cup \dots \cup S_{B}}$, що ${\displaystyle \sum _{i\in S_{k}}a_{i}\leq V}$ для всіх ${\displaystyle k=1,\dots ,B}$. Очевидно, що менше ${\displaystyle B}$, тим вигідніший розв'язок вдалося знайти. Найменше можливе ${\displaystyle B}$ надалі позначатимемо OPT.

Пакування як задача лінійного програмування

Задача пакування в ємності може бути задана як задача лінійного програмування наступним чином:

Мінімізувати ${\displaystyle B=\sum _{i=1}^{n}y_{i}}$
при обмеженнях	${\displaystyle \sum _{j=1}^{n}a_{j}x_{ij}\leq Vy_{i},}$	${\displaystyle \forall i\in \{1,\ldots ,n\}}$
	${\displaystyle \sum _{i=1}^{n}x_{ij}=1,}$	${\displaystyle \forall j\in \{1,\ldots ,n\}}$
	${\displaystyle y_{i}\in \{0,1\},}$	${\displaystyle \forall i\in \{1,\ldots ,n\}}$
	${\displaystyle x_{ij}\in \{0,1\},}$	${\displaystyle \forall i\in \{1,\ldots ,n\}\,\forall j\in \{1,\ldots ,n\}}$

де ${\displaystyle y_{i}=1}$, якщо ємність ${\displaystyle i}$ використовується, й ${\displaystyle x_{ij}=1}$, якщо предмет ${\displaystyle j}$ поміщено в ємність ${\displaystyle i}$.^[1]

Наближені поліноміальні алгоритми

Найпростішими поліноміальними алгоритмами пакування вважають алгоритми Best Fit Decreasing — BFD (Наліпший підходящий за спаданням) і First Fit Decreasing — FFD (Перший підходящий за спаданням). Предмети упорядковують за незростанням розміру й послідовно розміщують або в ємність, у якій після того залишиться якнайменший вільний об'єм — BFD, або в першу ємність, у які він входить (просторочо та/або за вагою) — FFD. Доведено, що ці алгоритми використають не більш як

${\displaystyle {\frac {11}{9}}OPT+1}$

ємностей^[2].

Однак для задачі упакування існують й асимптотично ε -оптимальні поліноміальні алгоритми.

Задача визначити, чи рівне OPT двом або трьом є NP-складною. Тому для довільного ε > 0 важко розмістити предмети до (3/2 − ε)OPT ємностей. (Якщо такий поліноміальний алгоритм існує, то за поліноміальний час можна визначити, чи розділиться n невід'ємних чисел на дві множини з однаковою сумою елементів. Однак відомо, що це питання NP-складне.) Відповідно, якщо P не збігається з NP, то для задачі упакування в ємності немає алгоритму схеми наближення до поліноміального часу (PTAS). З іншогобоку, для довільного ε >0  можна знайти рішення, як розмістити у не більш, ніж (1 + ε)OPT + 1 ємностей за поліноміальний час. Такі алгоритми відносять до асимптотичної PTAS.^[3] Але оскільки в оцінці склааності цього класу алгоритмів ${\displaystyle an^{b}}$ обидві константи довільно залежать від ε, подібні алгоритми, на відміну від FFD и BFD, насправді зовсім некорисні для життєвих задач.

Ймовірнісний підхід

Для певного класу ймовірнісного розподілу розмірів розміщених предметів, що включає опуклі вгору та внизу функції розподілу, існує практичний поліноміальний алгоритм пакування, асимптотично оптимальний майже напевне за необмеженого росту числа предметів. Для розподілів поза цим класом можна будувати власні поліноміальні асимптотичні оптимальні алгоритми.^[4].

Примітки

1. Silvano Martello and Paolo Toth (1990). Knapsack problems. Chichester, UK: John Wiley and Sons. с. 221. ISBN 0471924202.
2. Yue, Minyi (October 1991), A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm, Acta Mathematicae Applicatae Sinica, 7 (4): 321—331, doi:10.1007/BF02009683, ISSN 0168-9673 {{citation}}: Проігноровано |contribution= (довідка)
3. Fernandez de la Vega, W.; Lueker, G. S. (December 1981), Bin packing can be solved within 1 + ε in linear time, Combinatorica, Springer Berlin / Heidelberg, 1 (4): 349—355, doi:10.1007/BF02579456, ISSN 0209-9683 {{citation}}: Проігноровано |contribution= (довідка)
4. Смирнов А. В. Оптимізація процесу обробки даних в локальних мережах ЕОМ. — 1991.

Див. також

• Задача упаковки
• Задача про ранець
• Задача про суму підмножин
• Оптимізація
• Упаковка куль

Бібліографія

Джерела

• Бернард Корте, Єнс Вигон: Комбінаторна оптимізація. - Берлін/Хайдельберг: Спрінгер, 2008, ISBN 978-3-540-76918-7, Стор. 485

Мережеві посилання на матеріали

• PHP Class to pack files without exceeding a given size limit [Архівовано 27 грудня 2015 у Wayback Machine.]
• An implementation of several bin packing heuristics in Haskell [Архівовано 1 липня 2020 у Wayback Machine.], including FFD and MFFD.
• Cutting And Packing Algorithms Research Framework [Архівовано 31 грудня 2015 у Wayback Machine.], including a number of bin packing algorithms and test data.
• A simple on-line bin-packing algorithm
• Optimizing Three-Dimensional Bin Packing [Архівовано 5 березня 2016 у Wayback Machine.]
• Fpart : open-source command-line tool to pack files (C, BSD-licensed) [Архівовано 1 грудня 2015 у Wayback Machine.]
• Bin Packing and Cutting Stock Solver Algorithm [Архівовано 27 грудня 2015 у Wayback Machine.]

Увага! Бракує посилань на українські сайти. Хто їх знає - додайте їх сюди!

Перелік книг

1. Korf, Richard E. (2002), A new algorithm for optimal bin packing. (PDF), архів оригіналу (PDF) за 27 грудня 2015, процитовано 26 грудня 2015
2. Vazirani, Vijay V. (2003), Approximation Algorithms, Berlin: Springer, ISBN 3-540-65367-8
3. Yue, Minyi (October 1991), A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm, Acta Mathematicae Applicatae Sinica, 7 (4): 321—331, doi:10.1007/BF02009683, ISSN 0168-9673 {{citation}}: Проігноровано |contribution= (довідка)
4. Dósa, György (2007), The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I)≤(11/9)OPT(I)+6/9, у Chen, Bo; Paterson, Mike; Zhang, Guochuan (ред.), Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, т. 4614/2007, Springer Berlin / Heidelberg, с. 1—11, doi:10.1007/978-3-540-74450-4, ISBN 978-3-540-74449-8, ISSN 0302-9743
5. Xia, Binzhou; Tan, Zhiyi (2010), Tighter bounds of the First Fit algorithm for the bin-packing problem, Discrete Applied Mathematics, 158 (15): 1668—1675, doi:10.1016/j.dam.2010.05.026, ISSN 0166-218X {{citation}}: Проігноровано |contribution= (довідка)
6. Garey, Michael R.; Johnson, David S. (1985), A 71/60 theorem for bin packing*1, Journal of Complexity, 1: 65—106, doi:10.1016/0885-064X(85)90022-6 {{citation}}: Проігноровано |contribution= (довідка)
7. Yue, Minyi; Zhang, Lei (July 1995), A simple proof of the inequality MFFD(L)≤71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm, Acta Mathematicae Applicatae Sinica, 11 (3): 318—330, doi:10.1007/BF02011198, ISSN 0168-9673 {{citation}}: Проігноровано |contribution= (довідка)
8. Fernandez de la Vega, W.; Lueker, G. S. (December 1981), Bin packing can be solved within 1 + ε in linear time, Combinatorica, Springer Berlin / Heidelberg, 1 (4): 349—355, doi:10.1007/BF02579456, ISSN 0209-9683 {{citation}}: Проігноровано |contribution= (довідка)
9. Lewis, R. (2009), A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing, Computers and Operations Research, 36 (7): 2295—2310, doi:10.1016/j.cor.2008.09.004
10. Silvano Martello and Paolo Toth (1990), Knapsack Problems Algorithms and Computer Implementations.
11. Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A4.1: SR1, p. 226.
12. David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms [Архівовано 9 жовтня 2016 у Wayback Machine.]. SICOMP, Volume 3, Issue 4. 1974.
13. Lodi A., Martello S., Monaci, M., Vigo, D. (2010) Two-Dimensional Bin Packing Problems. In V.Th. Paschos (Ed.), “Paradigms of Combinatorial Optimization”, Wiley/ISTE, p. 107-129
14. Dósa G., Sgall J. (2013) First Fit bin packing: A tight analysis. To appear in STACS 2013.
15. Sindelar, Michael; Sitaraman, Ramesh; Shenoy, Prashant (2011), Sharing-Aware Algorithms for Virtual Machine Colocation, Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Jose, CA, June 2011: 367—378