Projeto E Analise De Algoritmos 2007 1 Projeto 2 Lower Bound

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.