Projeto E Analise De Algoritmos 2007 1 Projeto 2 Versao Do C

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 W_j $(j=1,...,n)$, sendo que cada W_j é 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 W_j$<=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 W_j $(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 [], 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 [].

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 [] 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];
}