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(); } ... }
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]; }
