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. O problema de decisão (decidir se um determinado número de pacotes é o ideal) é NP-completo.

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.

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

minimize $B=\sum _{i=1}^{n}y_{i}$
subject to	$B\geq 1,$
$\sum _{j=1}^{n}a_{j}x_{ij}\leq Vy_{i},$	$\forall i\in \{1,\ldots ,n\}$
$\sum _{i=1}^{n}x_{ij}=1,$	$\forall j\in \{1,\ldots ,n\}$
$y_{i}\in \{0,1\},$	$\forall i\in \{1,\ldots ,n\}$
$x_{ij}\in \{0,1\},$	$\forall i\in \{1,\ldots ,n\}\,\forall j\in \{1,\ldots ,n\}$

onde $y_{i}=1$se pacote $i$ for usado e $x_{ij}=1$e então $j$ é colocado no pacote $i$. ±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. 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). 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. MFFD (uma variante do FFD) não usa mais do que 71/60 OPT + 1 pacotes (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.

Algoritmo exato

Martello e Toth 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, e, mais tarde, melhorado; 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. 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

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  🔗 
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  🔗 

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