Generalized Upper Bound Branching

O generalized upper bound (GUB) branching é uma técnica de ramificação utilizada por algoritmos do tipo branch-and-bound.

Motivação

Imagine uma formulação contendo a seguinte desigualdade:

(1)

Suponha que o a relaxação linear foi resolvida e a variável possui valor fracionária e foi escolhida para ser ramificada. Assim, o algoritmo criará dois nós, um com e o outro com .

No nó com , a desigualdade (1) fica

(2)

Enquanto no nó com a desigualdade implicará que todas as outras variáveis terão valor 0.

Há uma diferença desproporcional em relação à redução do espaço de busca. No primeiro caso, a desigualdade (1) não permitiu fixar o valor de outra variável se não , enquanto no segundo, fixamos os valores de todas as variáveis envolvidas na desigualdade.

Uma das ramificações será resolvida rapidamente enquanto a outra continuará praticamente como o nó pai. Ou seja, é quase como se não tivéssemos efetuado a ramificação.

Esse tipo de degenerescência na árvore de busca é semelhante ao do algoritmo Quicksort, quando a escolha do pivô é tal que um dos subproblemas fica com quase todos os elementos e o outro com quase nenhum. Nesse caso a complexidade do algoritmo pode ficar .

Solução

Para contornar esse problema, existe uma estratégia chamada generalized upper bound, em que se tenta fixar não o valor de uma variável, mas o valor da soma de algumas delas. Para tentar manter a árvore de busca mais balanceada, vamos incluindo as primeiras variáveis em (1) até que a soma parcial deles ultrapasse 1/2. Matematicamente falando, sejam os valores das variáveis na relaxação linear. Então, seja

(3)

Criamos um nó adicionando a desigualdade

(4)

E outro com a desigualdade adicional

(5)

Xpress-Optmizer

O Xpress-Optimizer é um software proprietário que usamos no laboratório LOCo, capaz de resolver programas lineares inteiros mistos. Ele fornece esse tipo de estratégia, mas sob o nome de Special Ordered Set (SOS).

No Xpress, é preciso informar quais conjuntos de variáveis deverão sofrer ramificação da maneira apresentada acima. Além disso, para cada um desses conjuntos, é preciso passar o chamado “valor de referência” para cada variável. Segundo o manual do Xpress, esse valor é do tipo ponto flutuante e serve para ordenar as varáveis do conjunto. Se bem entendi, se é o valor de referência da variável i, ao invés de considerar ao calcular o somatório parcial, considera-se , onde representa uma permutação dos índices tal que , onde é o valor de referência de cada variável.

Citando o manual do Xpress, seção “Problem Types”:

Special ordered sets of type one (SOS1) — a set of non–negative decision variables ordered by a set of specified continuous values (or reference values) of which at most one can take a nonzero value. SOS1s are useful for modeling quantities that are taken from a specified discrete set of continuous values (e.g., choosing one of a set of transportation capacities);

Não está especificado no manual, mas os valores de referência devem ser distintos. A seção “Solution Methods”, ao explicar sobre o algoritmo de branch-and-bound também faz referência a SOS:

If the MIP problem contains SOS sets then the nodes of the Branch and Bound tree are separated by branching on the sets. Note that each member of the set has a double precision reference row entry and the sets are ordered by these reference row entries. Branching on the sets is done by choosing a position in the ordering of the set variables and setting all members of the set to 0 either above or below the chosen point. The optimizer used the reference row entries to decide on the branching position and so it is important to choose the reference row entries which reflect the cost of setting the set member to 0. In some cases it maybe better to model the problem with binary variables instead of sets. This is especially the case if the sets are small.

Note que a magnitude do valor de referência, além de determinar a ordem do somatório, influencia, de modo não especificado, na escolha do pivô (índice r em (3)) onde será feito a ramificação. Um chute seria que dentro do Xpress a escolha do pivô seja feita assim:

(6)

Na prática

Lembro-me de ter lido (vou ficar devendo a referência) que em casos onde a desigualdade (1) é usada para representar possíveis valores de uma variável, os valores de referência devem ser iguais a esses valores. Por exemplo:

(7)
(8)

Onde (8) serve para modelar que v pode valer 3, 5 ou 7. Então ao declarar que (8) deve sofrer GUB, é interessante usar como valor de referência .

Leitura complementar

[1] Special Ordered Sets (SOS) (Ver SOS1)

Os comentários estão fechados.

%d bloggers like this: