Projeto E Analise De Algoritmos 2007 1 Projeto 2

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.

Branch and Bound

A abordagem utilizada na resolução do BPP-1 foi a técnica de Branch-and-Bound, que consiste basicamente em um método exato enumerativo que explora apenas regiões do espaço de soluções onde existe a possibilidade de uma solução ótima ser encontrada. A chave para esta técnica é ter um bom critério para decidir se uma região do espaço de soluções pode conter uma solução ótima, o que o critério faz é resolver uma relaxação do problema, considerando o conjunto de decisões tomadas até o momento na construção da solução, obtendo um lower bound (no caso de um problema de minimização) que indica que as soluções daquela região não possuem valor inferior ao mesmo, e então comparar este valor com o valor da função objetivo da melhor solução encontrada até o momento da busca (upper bound). Caso o lower bound seja menor que o upper bound, então o algoritmo continua explorando aquela região em busca da solução ótima (branch), caso contrário o algoritmo não segue na exploração da região considerada (bound). Seguindo este framework é fundamental então trabalhar com boas técnicas de obtenção tanto de lower's quanto de upper's bound. Além disto é preciso decidir de que forma o espaço de soluções é explorado durante o algoritmo, ou seja, como é feito o particionamento do mesmo e em que ordem as regiões são exploradas. As seções seguintes descrevem justamente os elementos adotados no branch and bound para o BPP-1, ou seja, a forma em que o espaço de soluções é explorado, a determinação do upper bound inicial e os lower bound's utilizados no algoritmo.

Exploração do Espaço de Soluções

A estratégia adotada para a exploração do espaço de soluções cosistiu em percorrer a árvore de busca de forma recursiva como uma busca em profundidade, onde o particionamento do espaço consistia em colocar um determinado item em cada bin possível existente e colocá-lo também em um novo bin. Além disto a sequência de análise dos items segue uma ordem não decrescente de peso. O pseudo-código a seguir resume apenas a estratégia de exploração adotada no algoritmo:

// Recebe como parametros a solucao construida atualamente 
// e o item atual considerado
void branch-and-bound(Solucao &s, int itemAtual) {
    ...
    bool criou = false;
    // Percorre cada bin existente para tentar inserir o item atual nele
    for (int i=0; i<=s.nb; i++) {        
        // Se o item nao cabe no bin I, continua
        if (C - s.ocupado[i] < items[itemAtual]) continue;
 
        // Tenta colocar o item atual neste bin e chama recursivo
        s.bins[i].insert(itemAtual);
        s.ocupado[i] += items[itemAtual];
 
        // Cria novo bin
        if (i == s.nb) {
            s.nb += 1;
            criou = true;
        }
 
        // Chama recursivo para o proximo item
        branch-and-bound(s, itemAtual+1);
 
        // Desfaz as operacoes feitas para a chamada recursiva
        if (criou)
            s.nb -= 1;
        s.ocupado[i] -= items[step];
        s.bins[i].pop_back();
    }
    ...
}

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.

Solução viável inicial (Upper Bound Inicial)

Como explicado anteriormente é muito importante para o desempenho do branch and bound trabalhar com um upper bound que tenha valor o mais próximo do valor da função objetivo da solução ótima. Um upper bound, para um problema de minimização, nada mais é que o valor da função objetivo de alguma solução viável conhecida, assim para obtermos um bom upper bound basta gerar uma solução viável de boa qualidade através de qualquer método heurístico. Para o BPP-1 o upper bound inicial foi determinado em duas etapas. A primeira etapa consiste em construir duas soluções utilizando os métodos heurísticos gulosos first fit e best fit, sendo o upper bound atualizado para o menor valor obtido entre as duas soluções. A segunda etapa consiste em tentar encontrar um upper bound melhor através da busca por soluções viáveis para o BPP-1 pela resolução do BPP-2 em instâncias com número de bins entre o lower bound inicial e o upper bound da primeira etapa.

Métodos Gulosos

Os métodos gulosos da primeira etapa trabalham escolhendo a cada iteração em que bin um determinado item será inserido, até que todos os items estejam em algum bin sem estorar as capacidades dos mesmos. Assim a chave dos procedimentos é o critério que determina em que bin o item será inserido, os critérios de cada um são:

  • First-fit - A cada iteração, o item atual é armazenado no bin de menor índice que tenha capacidade residual suficiente para armazena-lo. Se não existe um bin com capacidade residual suficiente, então um novo bin é criado e o item é armazenado no mesmo.
  • Best-fit - A cada iteração, o item atual é armazenado no bin que tenha a menor capacidade residual suficiente para armazena-lo. Se houver empate o bin de menor índice é escolhido. Se não existe um bin com capacidade residual suficiente, então um novo bin é criado e o item é armazenado no mesmo.

Estratégia Dual via Busca Tabu

Para melhorar o upper bound obtido na primeira etapa foi desenvolvida a estratégia descrita em [1], que tem como elemento principal a meta-heurística busca tabu. A busca tabu é uma estratégia de busca local que tenta evitar a ciclagem entre soluções e o problema da busca ficar presa em um mínimo local. A descrição completa da busca tabu pode ser encontrada em [1].

A construção de uma busca tabu efetiva para o BPP-1 tem o problema de que as restições de capacidade restringem muito a busca e a definição usual de movimentos (mudar um item de bin ou trocar dois items entre bins diferentes) dificilmente afeta o valor da função objetivo. Como consequência, todos os movimentos possíveis em uma dada iteração tem muitas vezes o mesmo valor de função objetivo, não ficando claro qual movimento deve ser escolhido. Para lidar com este problema a estratégia proposta em [1] utiliza a relação próxima entre o BPP-1 e o BPP-2. Esta estratégia é chamada de dual, e pode ser descrita da seguinte forma: iniciando com o melhor valor de lower bound encontrado, tenta-se encontrar uma solução do BPP-2 para a instância tendo o número de bins igual ao do lower bound onde valor de sua função objetivo seja inferior a capacidade dos bins da instância original do BPP-1. Caso esta solução tenha sido encontrada ela o upper bound é então atualizado e o algoritmo termina. Caso contrário, aumenta-se o número de bins da instância do BPP-2 e novamente o resolve na busca de uma solução viável para o BPP-1. Este procedimento continua até que o número de bins da instância do BPP-2 se torna igual ao melhor upper bound já encontrado, se for este o caso o algoritmo para. A vantagem desta estratégia é que é mais natural se desenvolver um método heurístico de busca local como a busca tabu para resolver o BPP-2, já que o problema de similaridade da função objetivo entre soluções vizinhas é mínimo.

A estratégia para resolver as instâncias descritas do BPP-2 foi inicialmente gerar uma solução gulosa e em seguida aplicar a busca tabu. A solução gulosa simplesmente escolhia a cada iteração o bin que o item considerado seria armazenado como sendo o bin com o menor peso já armazenado, até que todos os items estivessem em algum bin. A busca tabu desenvolvida tem as seguintes características:

  • Vizinhança - De uma solução atual x, soluções vizinhas x' são obtidas através de dois tipos de movimentos simples. Ou um item $j$ é movido de seu bin atual $h$ para um novo bin $i$ (shift), ou dois items $j$ e $k$ são trocados de seus bins atuais $h$ e $i$ (swap).
  • Lista tabu - A lista tabu consiste de uma matriz de dimensões número de bins X número de items onde uma determinada posição $t[i][j]$ indica o status tabu do movimento que deseja armazenar o item $j$ no bin $i$. Quando é realizado um shift, o movimento de armazenar o item deslocado para a seu bin de origem é tornado tabu por um determinado número de iterações. Quando um swap é realizado os movimentos de retornar cada item para seu bin original são tornados também tabu. Um shift só é permitido se a mudança de bin do item não tem status tabu, já no swap as duas mudanças de bins não podem ter status tabu para que o mesmo seja permitido.
  • Seleção de movimento - O movimento escolhido em uma determinada iteração da busca é aquele que não tem status tabu e o que leva ao menor valor da função objetivo.
  • Critério de parada - O algoritmo para se um determinado número de iterações é atingido ou se a viabilidade da solução para o BPP-1 é alcançada.

O número de iterações em que o movimento fica tabu foi fixado em metade do número de items e limite de iterações do algoritmo foi fixado em dez vezes o número de items. O pseudo-código a seguir descreve em linhas gerais a estratégia dual:

// Procedimento principal da estrategia dual
int hybridUB(){
    // Itera sobre os valores que podem 
    // representar melhorias no Upper Bound
    for(int i=bestLower; i<bestUpper; i++){
        Solucao s;
        // Cria a solucao gulosa para o BPP-2
        int maxBin = criarDualWorstFit(s,i);
        // Se o bin mais pesado da solucao eh menor 
        // que a capacidade retorne o novo upper bound
        if(maxBin <= C) 
            return i;
        // Aplica a busca tabu na solucao gulosa
        maxBin = tabuSearch(s,i,N*10,N/2);
        // Se o bin mais pesado da solucao 
        // eh menor que a capacidade retorne o novo upper bound
        if(maxBin <= C) 
            return i;
    }
}
 
// Procedimento de busca tabu para o BPP-2
int tabuSearch(Solucao & s, int nb, int numIter, int tabuTenure){
    Inicializa a tabuList;
    bool viavel = false;
    for(int iter=0; iter<numIter && !viavel; iter++){
        move = escolhe o melhor movimento nao tabu;
        if(move.moveType == SHIFT){
            realiza o shift entre do item a do bin h para o bin k;
 
            torna o movimento de armazenar a em h como 
            tabu pelas proximas tabuTenure iteracoes;
        }
        else if(moveType == SWAP){
            realiza o swap entre item a do bin h e o item b do bin k;
 
            torna o movimento de armazenar o item a no bin h 
            como tabu pelas proximas tabuTenure iteracoes;
 
            torna o movimento de armazenar o item b no bin k 
            como tabu pelas proximas tabuTenure iteracoes;
        }
        // Se o maior peso total armazenado em um bin eh menor 
        // que a capacidade do mesmo a soucao eh viavel para o BPP-1
        if(atual.ocupado[atual.heaviestBin] <= C)
            viavel = true;
    }
    return s.ocupado[s.heaviestBin];
}

Resultados

O algoritmo foi testado sobre as instâncias encontradas na página http://www.wiwi.uni-jena.de/Entscheidung/binpp/. Estas instâncias se dividem em três conjuntos, para a realização dos testes foram coletadas 510 instâncias entre as instâncias do primeiro e do segundo conjunto, que são similares, e também todas as 10 instâncias do terceiro conjunto. As 510 instâncias dos conjuntos 1 e 2 foram testadas usando como limite de tempo de execução 2 minutos, já as 10 instâncias do terceiro conjunto foram testadas com um limite de tempo de execução de 5 minutos, pois as mesmas são consideradas mais complexas. Em anexo são apresentadas as tabelas dos resultados obtidos nos dois conjuntos de teste, estas tabelas contém os melhores upper e lower bound obtidos, os tempos de execução da fase de construção da solução inicial e do branch em bound em si, e o status que indica se o algoritmo encontrou de forma comprovada uma solução ótima (isto ocorre ou quando o upper bound se torna igual ao lower bound ou quando a enumeração do Branch and Bound se encerra).

Os resultados dos testes mostram que na maioria dos casos o upper bound e o lower bound iniciais já coincidem e que portanto uma solução ótima foi encontrada sem haver a necessidade de executar o branch em bound. Nos casos em que o branch and bound é executado, notamos que poucos deles conseguem chegar ao fim da exploração da árvore de busca, onde isto se torna mais raro com o aumento do tamanho das instâncias. Estes resultados mostram que as técnicas de upper e lower bound's aplicadas foram bastante efetivas, já que em muitos casos não existe a necessidade de se executar o branch and bound, até mesmo em 3 das 10 instâncias do conjunto 3, que são consideradas complexas. Como nos casos em que o branch and bound é executado ele obtém pouco sucesso, devemos esta fato a grande complexidade de resolução do problema de bin packing, um problema np-difícil, e principalmente a uma possível má escolha na estratégia de exploração do espaço de busca. Um futuro trabalho seria investigar outras estratégias para exploração do espaço de busca, onde provavelmente os resultados encontrados seriam melhores.

Referências

1 - Scholl, Klein Jürgens - Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem

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