Branch and Bound: Seleção de variável

Um aspecto que pode influenciar o desempenho de um algoritmo de Branch and Bound é a escolha da variável que sofrerá branching. Para relembrar, em cada nó da árvore de exploração do Branch and Bound, resolve-se a relaxação linear do modelo, o que, na maioria das vezes, retorna uma solução fracionária.

A ideia é então escolher uma variável com valor fracionário por exemplo, e criar dois novos modelos, um com a restrição e outro com a restrição .

A questão é, qual a melhor variável para se escolher? Uma regra bem simples é escolher aquela com valor “mais fracionário”, ou seja, cuja parte decimal seja mais próxima de 0.5, desempatando arbitrariamente. Porém há pelo menos duas técnicas mais sofisticadas que iremos apresentar a seguir.

Strong Branching

O strong branching é basicamente o seguinte. Para cada variável, calculamos o valor da relaxação linear do PL com a restrição e do PL com a restrição , chamando-os respectivamente de e . Observe que ambos são limitantes duais para o problema. Calculamos uma soma ponderada desses dois valores e escolhemos a variável com valor mais apertado (ou seja, menor valor se o proplema é de maximização ou maior se é de minimização).

O problema dessa abordagem é o custo. Resolver duas relaxações lineares para cada variável em cada nó é bastante custoso. Uma abordagem aproximada consiste em pegar apenas as N variáveis “mais fracionárias” para fazer tal cálculo. Além do mais, executar no máximo K iterações do algoritmo dual-simplex e não até encontrar a solução ótima.

Pseudo-custos

Outra alternativa mais barata é o uso de pseudo-custos, que são uma estimativa dos valores e do strong branching. Essa estimativa é essencialmente a média obtida dos valores das relaxações lineares ao longo da execução do algoritmo ao fazer o branching das variáveis. Assim, se em um dado momento o algoritmo escolhe a variávei i para sofrer branching, analisamos os valores das relaxações lineares de seus filhos e atualizamos essas médias para i.

Para termos um valor inicial das estimativas de e , podemos aplicar o strong branching apenas na raíz.

Prioridades

Há vezes em que sabemos, por teoria, que fazer branching em uma certa classe de variável primeiro, tende a gerar árvores de busca de menor altura. Logo, um vetor de prioridades de cada variável fornecido como parte do modelo pode ser usado para guiar a escolha do algoritmo de Branch and Bound.

Como veremos a seguir, a biblioteca XPRESS trabalha com o conceito de prioridades e pseudo custos.

Seleção da variável no XPRESS

Segundo o manual, a biblioteca XPRESS trabalha com dois parâmetros para cada variável: a prioridade (o padrão é 500) e os pseudo-custos (up e down). O trecho a seguir, extraído desse manual, explica o algoritmo:

Each global entry has a priority for branching, either the default value of 500 or one set by the user in the directives file. A low priority value means that the variable is more likely to be selected for branching. Up and down pseudo costs for each global entity can be specified, which are estimates of the per unit degradation of forcing the entity away from its LP value.

The Optimizer selects the branching entity from among those entities of the most important priority class which remain unsatisfied. Of these, it takes the one with the highest estimated cost of being satisfied (degradation).

O algoritmo divide as variáveis em classe de prioridades. Pertencem à mesma classe aquelas variáveis que possuem mesma prioridade. O algoritmo então escolhe a classe com menor valor de prioridade que tenha pelo menos uma varíavel fracionária. Para escolher a variável dentro dessa classe, ele utiliza os pseudo-custos como critério de desempate.

Ele define o valor de degradação como uma combinação dos pseudo-custos up e down de cada variável. Qual a conta feita depende do parâmetro VARSELECTION, mas algumas delas são: min(up, down), up + down e min(up, down) + max(up, down). Então, ele seleciona a variável com maior valor de degradação.

Referências

[1] Notas de aula sobre Programação Inteira por Jeff Linderoth

[2] Encyclopedia of Optimization, 2nd Edition – Chapter: Integer Programming: Branch and Bound Methods, Branching Variable Selection

Os comentários estão fechados.

%d bloggers like this: