# 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, $$. Porque $$ é 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

* ↑ 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
* ↑ Barrington, David Mix (2006). «Bin Packing»
* ↑ Lewis 2009
* ↑ Sindelar, Sitaraman & Shenoy 2011, pp. 367–378
* ↑ Martello & Toth 1990, p. 221
* ↑ Vazirani 2003, p. 74.
* ↑ Yue 1991, pp. 321–331.
* ↑ Dósa 2007, pp. 1–11.
* ↑ Garey & Johnson 1985, pp. 65–106.
* ↑ Yue & Zhang 1995, pp. 318–330.
* ↑ Vazirani 2003, pp. 74–76.
* ↑ Fernandez de la Vega & Lueker 1981, pp. 349–355
* ↑ Martello & Toth 1990, pp. 237–240.
* ↑ Korf 2002
* ↑ R. E. Korf (2003), An improved algorithm for optimal bin packing.
* ↑ Schreiber & Korf 2013
Bibliografia
* 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) 🔗
* Vazirani, Vijay V. (2003), Approximation Algorithms, ISBN 3-540-65367-8, Berlin: Springer
* 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
* 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
* 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
* 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
* 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
* 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
* 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
* Martello, Silvano; Toth, Paolo (1990), «Bin-packing problem» (PDF), Knapsack Problems: Algorithms and Computer Implementations, ISBN 0471924202, Chichester, UK: John Wiley and Sons
* 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.
* 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.
* 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
* Dósa G., Sgall J. (2013) First Fit bin packing: A tight analysis. To appear in STACS 2013.
* 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.
* 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
* 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) 🔗