Problema do empacotamento

Predefinição:Wikificação 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\le 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\ge 1,$
$\sum _{j=1}^n{a}_j{x}_{ij}\le V{y}_i,$	$\mathrm{\forall }i\in \{1,\dots ,n\}$
$\sum _{i=1}^n{x}_{ij}=1,$	$\mathrm{\forall }j\in \{1,\dots ,n\}$
$y_i\in \{0,1\},$	$\mathrm{\forall }i\in \{1,\dots ,n\}$
$x_{ij}\in \{0,1\},$	$\mathrm{\forall }i\in \{1,\dots ,n\}\mathrm{\forall }j\in \{1,\dots ,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 Predefinição:Nowrap 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

Predefinição:ReflistBibliografia

1. Predefinição:Citation
2. Predefinição:Citation
3. Predefinição:Citation
4. Predefinição:Citation
5. Predefinição:Citation
6. Predefinição:Citation
7. Predefinição:Citation
8. Predefinição:Citation
9. Predefinição:Citation
10. Predefinição:Citation
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. Predefinição:Citation
17. Predefinição:Citation

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