Projeto E Analise De Algoritmos 2007 1 Projeto 2 Definicao D

Definição do problema

O problema de bin packing em uma dimensão (BPP) é definido como:

  • Dado um conjunto $J={1,...,n}$ de $n$ itens não particionáveis, cada um com um tamanho ou peso específico Wj $(j=1,...,n)$, sendo que cada Wj é um inteiro, sem perda de generalidade.

O problema consiste em empacotar cada item em um dos $m$ bins(lixeiras), sendo que cada bin possui capacidade máxima $c$. Ou seja, a soma dos itens inseridos em um bin não pode exceder este limite (uma condição necessária então é que Wj$<=c$ para todo $j$).

Podemos desse modo distinguir duas versões do problema:

  • BPP-1: Minimizar o número $m$ de bins para uma dada capacidade $c$.
  • BPP-2: Minimizar a capacidade $c$ para um dado número $m$ de bins.

As duas versões do problema são problemas de otimização NP-Difíceis. Os dois problemas são baseados no problema de decisão de descobrir se existe ou não uma solução possível para uma dada combinação de $c$ e $m$.

Este projeto baseou-se na versão de otimização do BPP-1, utilizando Branch and Bound para busca da solução ótima.

Análise de complexidade

BPP-1 é NP-Difícil

Enunciamos que o bin packing é um problema NP-Difícil. Em outras palavras, estamos dizendo que não se conhece um algoritmo polinomial para a versão de decisão do BPP-1:

  • dados $n$ itens, cada um com peso inteiro Wj $(j=1,...,n)$, e inteiros $m$ e $c$, decidir se existe uma solução viável para o problema de armazenar os $n$ itens nos $m$ bins com capacidade $c$ cada.

Para provar esta afirmação de que BPP-1 $\in$ NP-Difícil, basta reduzirmos um problema $P1$ conhecidamente pertencente à classe de problemas NP-Difícil ao problema BPP-1.

Para esta prova, foi escolhido o problema Partition, cuja definição de sua versão de decisão é dada a seguir:

  • Dado um multiconjunto $V$ de $n$ inteiros, decidir se existe um subconjunto $S \subseteq V$ tal que $\sum_{x \in S} x = \sum_{y \in V-S} y$.

Redução do problema Partition para o BPP-1

Dada uma instância de Partition, ou seja, dado um multiconjunto $V$ de $n$ inteiros, criamos uma instância do BPP-1 da seguinta forma:

  • $n = |V|$
  • pesos W $= V$
  • $c = \frac{\sum_{x \in V} x}{2}$
  • $m = 2$

Se o BPP-1 responde sim, significa que existe uma solução viável para armazenar os $n = |V|$ itens de pesos W $= V$ nos 2 bins de capacidade c = $\frac{\sum_{x \in V} x}{2}$ cada.

Já que a soma total dos pesos dos $n$ itens é $2c$ e que todos os itens podem ser armazenados nos 2 bins disponíveis, necessariamente a soma dos itens de cada bin é exatamente igual a c.

Desse modo, é nítido que existe um particionamento do multiconjunto $V$ tal que a soma dos itens de uma partição seja igual à soma dos itens da outra partição: basta escolher os itens armazenados em um dos bins para ser o subconjunto $S$, e os itens do outro bin para denotar $V - S$. Em outras palavras, se o BPP-1 responde sim para uma determinada instância definida como acima, necessariamente o problema Partition também responde sim.

De modo inverso, caso exista uma partição do multiconjunto $V$ em um subconjunto $S$ (cuja soma de itens é $c$) e outro subconjunto $V - S$ (cuja soma de itens também é $c$), se fizermos a redução conforme definida mais acima, o problema BPP-1 também responderá sim, já que será possível armazenar os $|V|$ itens de peso W $= V$ nos m = 2 bins de capacidade $c$ cada: basta armazenar todos os itens de $S$ em um bin e todos os itens de $V - S$ no outro bin. Em outras palavras, se o problema Partition responde sim para uma determinada instância, necessariamente o BPP-1 também responderá sim caso seja usada a redução como definida acima.

Lower Bounds (Relaxações)

Um lower bound de um dado nó da árvore de busca do branch and bound para um problema de minimização pode ser entendido como:

  • uma estimativa do menor valor possível que pode ser atingido por uma solução, dado que um conjunto de decisões sobre a resolução do problema já tenham sido tomadas

O lower bound então é sempre menor ou igual ao valor da melhor solução possível, dadas as decisões já tomadas. Esta estimativa é interessante porque permite ao algoritmo deixar de explorar certos ramos da árvore de busca, tendo a certeza de que não haverá perda de soluções melhores que as já encontradas.

No branch and bound para o BPP-1 foram adotados dois lower bounds bem conhecidos da literatura do problema [1], o LB1 e o LB2. A utilização dos dois foi feita para tentar obter um lower bound de melhor qualidade: o maior valor entre o LB1 e o LB2 é escolhido como lower bound do nó.

As seções a seguir descrevem o LB1 e o LB2.

Lower Bound LB1

Para definir um lower bound simples para o BPP-1, podemos usar a relaxação de que é possível dividir os itens a serem armazenados. Ou seja, retiramos a restrição de que os itens não são particionáveis, e permitimos que um item seja dividido entre 2 ou mais bins diferentes. Sendo assim, o LB1 é definido como:

  • $LB1 = \lceil \sum_{j=1}^n \frac{Wj}{c} \rceil$

Lower Bound LB2

Este outro possível lower bound para o BPP-1 é baseado no particionamento do conjunto de itens a serem armazenados em 3 subconjuntos de acordo com um parâmetro inteiro $\alpha \in [0,c/2]$:

  • $J1 = \{j \in J|Wj > c - \alpha\}$
  • $J2 = \{j \in J|c/2 < Wj \leq c - \alpha\}$
  • $J3 = \{j \in J|\alpha \leq Wj \leq c/2\}$

Podemos anunciar as seguintes propriedades interessantes de cada um destes subconjuntos gerados pelo particionamento proposto:

  • Já que $\alpha \in [0,c/2]$, $J1$ é composto por itens muito grandes, com peso $Wj \geq c/2$. Desse modo, nenhum par de itens pertencentes a $J1$ podem ser armazenados no mesmo bin.
  • Nenhum item de $J2$ pode ser armazenado no mesmo bin em que haja um item de $J1$, uma vez que a soma de seus pesos $t$ resulta em $t > c - \alpha + c/2 = 3c/2 - \alpha > c$, o que excederia a capacidade do bin.

Podemos então definir:

  • $L(\alpha) = |J1| + |J2| + max\{0,\[\frac{\sum_{j \in J3}Wj - (|J2|c - \sum_{j \in J2}Wj)},c\]\}$

Desse modo, podemos definir o LB2 como sendo:

  • $LB2 = max\{L(\alpha) | 0 \leq \alpha \leq c/2\}$

Como dito, max{LB1,LB2} foi usado como o lower bound de um determinado nó no branch and bound.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.