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

Нехай дана множина ємностей розміру ${\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].

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

• PHP Class to pack files without exceeding a given size limit
• An implementation of several bin packing heuristics in Haskell, including FFD and MFFD.
• Cutting And Packing Algorithms Research Framework, including a number of bin packing algorithms and test data.
• A simple on-line bin-packing algorithm
• Optimizing Three-Dimensional Bin Packing
• Fpart : open-source command-line tool to pack files (C, BSD-licensed)
• Bin Packing and Cutting Stock Solver Algorithm

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

1. Korf, Richard E. (2002). A new algorithm for optimal bin packing. AAAI-02. Архів оригіналу за 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, for all L, for the FFD bin-packing algorithm. 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. ISSN 0168-9673. doi:10.1007/BF02009683.
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. ISBN 978-3-540-74449-8. ISSN 0302-9743. doi:10.1007/978-3-540-74450-4.
5. Xia, Binzhou; Tan, Zhiyi (2010). Tighter bounds of the First Fit algorithm for the bin-packing problem. Tighter bounds of the First Fit algorithm for the bin-packing problem. Discrete Applied Mathematics 158 (15): 1668–1675. ISSN 0166-218X. doi:10.1016/j.dam.2010.05.026.
6. Garey, Michael R.; Johnson, David S. (1985). A 71/60 theorem for bin packing. A 71/60 theorem for bin packing*1. Journal of Complexity 1: 65–106. doi:10.1016/0885-064X(85)90022-6.
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. 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. ISSN 0168-9673. doi:10.1007/BF02011198.
8. Fernandez de la Vega, W.; Lueker, G. S. (December 1981). Bin packing can be solved within 1 + ε in linear time. Bin packing can be solved within 1 + ε in linear time. Combinatorica (Springer Berlin / Heidelberg) 1 (4): 349–355. ISSN 0209-9683. doi:10.1007/BF02579456.
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. 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.