Problema do empacotamento

No problema de bin packing (ou problema do empacotamento), objetos de diferentes volumes devem ser embalados em um número finito de bandejas ou recipientes de volume V de uma forma que minimize o número de recipientes utilizados. Na teoria da complexidade computacional, este é um problema de combinatória NP-difícil.^[1] O problema de decisão (decidir se um determinado número de pacotes é o ideal) é NP-completo.^[2]

Existem muitas variações deste problema, tais como empacotamento 2D (2D packing), empacotamento linear (linear packing), empacotamento por peso (packing by weight), empacotamento por custo (packing by cost), e assim por diante. Eles tem muitas aplicações, tais como o enchimento de recipientes, carregamento de caminhões com peso com capacidade restrita, criação de arquivo de backup (cópias de segurança) em mídia.

O problema  do empacotamento também pode ser visto como um caso especial do problema de corte de estoque (cutting stock problem). Quando o número de pacotes é restrito a 1 e cada item é caracterizado por um volume e um valor, o problema de maximização do valor dos itens que podem caber na lixeira é conhecida como a problema da mochila.

Apesar do fato de que o problema do empacotamento tem uma complexidade computacional uma NP-difícil, as melhores soluções para grandes instâncias do problema pode ser produzido com algoritmos sofisticados. Além disso, muitas heurísticas foram desenvolvidas: por exemplo, o algoritmo de first fit fornece uma solução rápida, mas muitas vezes não ideal, envolvendo colocar-se cada item para a primeira posição que couber. Ele requer custo de tempo Θ(n log n), onde n é o número de elementos a ser empacotados. O algoritmo pode ser tornado mais eficaz se primeiramente  ordenar a lista de elementos em ordem decrescente (às vezes conhecida como o algoritmo first-fit decrescente), embora isso ainda não garante uma solução ótima, e para longas listas pode aumentar o tempo de execução do algoritmo. Sabe-se, contudo, que existe sempre pelo menos um ordenamento de itens que o first-fit produzir uma solução ótima.^[3]

Um variante do bin packing que ocorre na prática é quando os itens podem compartilhar o espaço quando empacotados em uma caixa. Especificamente, um conjunto de itens pode ocupar menos espaço quando embaladas em conjunto do que a soma de seus tamanhos individuais. Esta variante é conhecida como VM packing^[4] desde quando máquinas virtuais (VMs) são embaladas em um servidor, o total de sua memória gerenciada pode diminuir devido às páginas compartilhadas pelas VMs as quais precisam ser armazenados apenas uma vez. Se os itens podem dividir o espaço de maneiras arbitrárias, o problema do empacotamento é difícil, mesmo de forma aproximada. No entanto, se o compartilhamento de espaço se encaixa em uma hierarquia, como é o caso de compartilhamento de memória em máquinas virtuais, o problema do empacotamento pode ser eficientemente aproximado.

Declaração Formal

Dado um conjunto de pacotes (bins) ${\displaystyle S_{1},S_{2}...}$ de um mesmo tamanho ${\displaystyle V}$ e uma lista de ${\displaystyle n}$ itens com tamanhos ${\displaystyle a_{1},\,\dots ,\,a_{n}}$ para empacotar, encontre um número inteiro de bins ${\displaystyle B}$ e uma ${\displaystyle B}$-partição ${\displaystyle S_{1}\cup \cdots \cup S_{B}}$ do conjunto ${\displaystyle \{1,\,\dots ,\,n\}}$ tal que ${\displaystyle \sum _{i\in S_{k}}a_{i}\leq V}$ ${\displaystyle k=1,\,\dots ,\,B.}$ A solução é ótimo se possui um ${\displaystyle B}$. O valor de ${\displaystyle B}$para uma solução ótima é denotado como OPT abaixo. Uma possível formula mesclada de programação linear com inteiros é:

minimize ${\displaystyle B=\sum _{i=1}^{n}y_{i}}$
subject to	${\displaystyle B\geq 1,}$
${\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\}}$

onde ${\displaystyle y_{i}=1}$se pacote ${\displaystyle i}$ for usado e ${\displaystyle x_{ij}=1}$e então ${\displaystyle j}$ é colocado no pacote ${\displaystyle i}$.^[5] ±https://pt.wikipedia.org/w/index.php?title=Problema_do_empacotamento&action=edit&section=1 {{hushijkam/kmkna<lozxpk>paoocpalp´lpçll/lock</focautl>

Algoritmo de first-fit

Este é um algoritmo de aproximação muito simples, o algoritmo guloso. O algoritmo processa os itens em ordem arbitrária. Para cada item, ele tenta colocar o item no primeiro pacote que pode acomodá-lo. Se nenhum pacote é encontrado, ele abre um novo pacote e coloca o item dentro deste novo pacote.

É bastante simples para mostrar este algoritmo, obtém-se um fator de aproximação de 2, isto é, o número de pacotes utilizados por este algoritmo não é mais do que duas vezes o número ideal. Em outras palavras, é impossível para 2 pacotes estarem preenchidos no máximo pela metade, pois tal possibilidade implica que em algum ponto, exatamente um pacote foi no máximo cheio até a metade e um nov foi aberto para acomodar um item de tamanho de no máximo V/2. Mas desde que o primeiro tem, pelo menos, um espaço de V / 2, o algoritmo não abrirá um novo pacote para qualquer item cujo tamanho é de, no máximo, V / 2. Só depois de o pacote encher-se com mais do que o V / 2, ou se um item com um tamanho maior do que o V / 2 chega, o algoritmo pode abrir uma nova posição.

Assim, se temos B bandejas, pelo menos B − 1 bandejas estão cheias mais que a metade do total. Portanto, ${\displaystyle }$. Porque ${\displaystyle }$ é um limite inferior do valor ideal OPT, temos que B − 1 < 2OPT e, portanto, B ≤ 2OPT.^[6] Veja a análise abaixo para uma melhor aproximação dos resultados.

Prova alternativa:

Suponha que o algoritmo guloso retorna mais de 2 OPT pacotes. Se tomarmos quaisquer dois pacotes sucessivos, juntos, eles devem conter, pelo menos, V de itens (caso contrário, apenas um pacote seria o suficiente para estes itens). Desde que nós temos, no mínimo, OPT pares mais pacotes extra, nós, em conjunto, teríamos mais do que OPT V itens, que seria uma contradição.

Algoritmos de Aproximação

As estratégias best fit e o first fit estão entre os mais simples algoritmos heurísticos para resolver o problema do empacotamento. Eles foram provados que não utilizam mais de 11/9 OPT + 1 pacotes (onde OPT é o número de posições dadas pela solução ótima).^[7] O mais simples destes, a estratégia First Fit Decrescente(FFD), onde opera primeiramente ordenando os itens a serem inseridos em ordem decrescente por seus tamanhos e, em seguida, inserir cada item para o primeiro pacote na lista com espaço suficiente restante. Às vezes, no entanto, não se tem a opção de classificar a entrada, por exemplo, quando nos deparamos com um problema online de empacotamento. Em 2007, foi comprovado que o limite 11/9 OPT + 6/9 para a FFD é Grande-O.^[8] MFFD^[9] (uma variante do FFD) não usa mais do que 71/60 OPT + 1 pacotes^[10] (i.e. delimitada por cerca de 1.18 OPT, em comparação com cerca de 1,22 OPT por FFD). Em 2013, Sgall e Dósa deu um limitante superior para a estratégia first-fit (FF), mostrando que ele nunca precisa mais do que 17/10 OPT posições, para qualquer entrada.

É NP-difícil para distinguir se OPT é 2 ou 3, assim, para todo ε > 0, problema do empacotamento é difícil de aproximar cerca de 3/2 − ε. (Se tal aproximação, existe, pode determinar se n inteiros não negativos pode ser particionado em dois conjuntos com a mesma soma em tempo polinomial. No entanto, esse problema é conhecido por ser NP-difícil.) Consequentemente, o problema do empacotamento não tem um esquema de tempo polinomial de aproximação (APMS), a menos que P = NP. Por outro lado, para qualquer 0 < ε ≤ 1, é possível encontrar uma solução usando não mais do que (1 + ε)OPT + 1 pacote em tempo polinomial. Este tipo de aproximação é conhecida como assintótico PTAS.^[11][12]

Algoritmo exato

Martello e Toth^[13] desenvolveram um algoritmo exato para o 1-D problema do empacotamento, chamado de MTP. Uma alternativa mais rápida é a algoritmo Conclusão de Pacotes (Bin Completion) proposto por Korf, em 2002,^[14] e, mais tarde, melhorado;^[15] este segundo livro relata o tempo médio para resolver um milhão de ocorrências, com 80 itens em um 440 MHz Sun Ultra com 10 workstation foi de 31 ms.

Outra melhoria foi apresentada por Schreiber e Korf em 2013.^[16] A novo e melhorado algoritmo Conclusão de Pacotes é mostrado para ser de até cinco ordens de magnitude mais rápido que Conclusão de Pacotes antigo sobre problemas não-triviais com 100 itens, e supera o BCP (branch-and-cut-and-price) algoritmo por Belov e Scheithauer em problemas que têm menos de 20 pacotes como a solução ideal. Qual o algoritmo tem o melhor desempenho depende das propriedades do problema, como o número de itens, o número ideal de pacotes, o espaço não utilizado na solução ótima e precisão de valores.

Veja também

• Se o número de caixas é para ser fixo ou restrito, e o tamanho das caixas é para ser o mínimo, este é um problema diferente, que é equivalente ao problema de programação com múltiplos processadores
• Guilhotina problema
  
• Subconjunto soma problema

Referencias

1. Korte, Bernhard; Vygen, Jens (2006). «Bin-Packing». Combinatorial Optimization: Theory and Algorithms. Col: Algorithms and Combinatorics 21. [S.l.]: Springer. pp. 426–441. ISBN 978-3-540-25684-7. doi:10.1007/3-540-29297-7_18 
2. Barrington, David Mix (2006). «Bin Packing» 
3. Lewis 2009
4. Sindelar, Sitaraman & Shenoy 2011, pp. 367–378
5. Martello & Toth 1990, p. 221
6. Vazirani 2003, p. 74.
7. Yue 1991, pp. 321–331.
8. Dósa 2007, pp. 1–11.
9. Garey & Johnson 1985, pp. 65–106.
10. Yue & Zhang 1995, pp. 318–330.
11. Vazirani 2003, pp. 74–76.
12. Fernandez de la Vega & Lueker 1981, pp. 349–355
13. Martello & Toth 1990, pp. 237–240.
14. Korf 2002
15. R. E. Korf (2003), An improved algorithm for optimal bin packing.
16. Schreiber & Korf 2013

Bibliografia

1. Korf, Richard E. (2002), A new algorithm for optimal bin packing. (PDF), consultado em 8 de julho de 2016, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda) 🔗 
2. Vazirani, Vijay V. (2003), Approximation Algorithms, ISBN 3-540-65367-8, Berlin: Springer 
3. Yue, Minyi (outubro 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, ISSN 0168-9673, 7 (4): 321–331, 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», in: Chen, Bo; Paterson, Mike; Zhang, Guochuan, Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ISBN 978-3-540-74449-8, Springer Berlin / Heidelberg, ISSN 0302-9743, 4614/2007, pp. 1–11, 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», Discrete Applied Mathematics, ISSN 0166-218X, 158 (15): 1668–1675, doi:10.1016/j.dam.2010.05.026 
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 
7. Yue, Minyi; Zhang, Lei (julho 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, ISSN 0168-9673, 11 (3): 318–330, doi:10.1007/BF02011198 
8. Fernandez de la Vega, W.; Lueker, G. S. (dezembro 1981), «Bin packing can be solved within 1 + ε in linear time», Springer Berlin / Heidelberg, Combinatorica, ISSN 0209-9683, 1 (4): 349–355, 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. Martello, Silvano; Toth, Paolo (1990), «Bin-packing problem» (PDF), Knapsack Problems: Algorithms and Computer Implementations, ISBN 0471924202, Chichester, UK: John Wiley and Sons 
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. Benkő A., Dósa G., Tuza Z. (2010) Bin Packing/Covering with Delivery, Solved with the Evolution of Algorithms, Proceedings 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010, art. no. 5645312, Pages 298-302.
16. 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 
17. Schreiber, Ethan L.; Korf, Richard E. (2013), Improved Bin Completion for Optimal Bin Packing and Number Partitioning (PDF), ISBN 978-1-57735-633-2, IJCAI '13, Beijing, China: AAAI Press, pp. 651–658, consultado em 8 de julho de 2016, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda) 🔗 

Ligações externas

• PHP Class to pack files without exceeding a given size limit
• An implementation of several bin packing heuristics in Haskell, incluindo FFD e MFFD.
• Visualization of heuristics for 1D and 2D bin packing
• Cutting And Packing Algorithms Research Framework, incluindo o número de algoritmos de Bin Packing e os dados dos testes.
• 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