AULA COMPUTACIONAL
- Síntese de Sistemas de Separação
(Cap. 7)
20 DE OUTUBRO DE 2008
7.6 Resolução por Método de Busca Orientada por Árvore de
Estados
7.6.1 Descrição do Método de Rodrigo & Seader
7.6.2 Resolução do Problema Ilustrativo pelo Método de
Rodrigo & Seader
Sequenciamento de destilações.












 















Localização de alimentação e/ou refluxo de colunas de destilação



Rede de trocadores de calor
Problemas com o relaxamento da variáveis inteiras
As variáveis inteiras, z, com limites superiores e inferiores dados, zl
 z  zu, podem ser expressas como um vetor de variáveis binárias, y
 Y = {0,1}q, pela seguinte fórmula:
z  z l  y1  2 y 2  4 y3    2 q 1 y q
onde q é o número mínimo de variáveis 01 necessárias para
representar z. Este número mínimo é dado por:

u
l

 log z  z
q  1  int

 log 2



sendo que a função “int” trunca o argumento real para um valor inteiro.
Programação linear inteira mista (MILP)
min cT x + dT y
sujeito a: A x + B y  b
x0
x  X  n, y  Y = {0,1}q
Método de Branch & Bound
O método de branch and bound está baseado nas idéias chaves de:
Separação
Relaxação
Sondagem
Separação
Denotando o problema MILP abaixo por (P) e o conjunto de suas
soluções viáveis por FS(P).
Então o conjunto de subproblemas (P1), (P2), ..., (Pn) de (P) é uma separação de
(P) se:
(i)
uma solução viável de qualquer subproblema (P1), (P2), ..., (Pn) é
também uma solução viável de (P);
(ii)
cada solução viável de (P) é uma solução viável de exatamente um de
seus subproblemas.
Neste caso, o problema (P) é chamado de problema Pai e os subproblemas
(P1), (P2), ..., (Pn) são chamados de problemas Filhos.
Uma questão importante no método de branch and bound é de como
gerar uma separação do problema (P).
A maneira geralmente utilizada é a introdução de restrições
contraditórias em uma única variável binária (ou inteira) a cada estágio.
Por exemplo, selecionando a variável binária y1 de (P), pode-se separálo, ou ramificá-lo (branching), em dois subproblemas (P1) e (P2):
Relaxação
Um problema de otimização, denotado por (RP), é uma
relaxação do problema (P) se o conjunto de soluções viáveis de (P) é um
subconjunto de soluções viáveis de (RP), isto é,
FS(P)  FS(RP)
Deste modo, se (RP) não tem solução viável, então (P) também não tem.
Além disto, se zP é a solução ótima de (P) e zRP é a solução ótima de
(RP), então:
zRP  zP
ou seja, a solução do problema relaxado fornece um limite inferior para a
solução do problema original. Naturalmente, se a solução ótima de (RP)
é viável para (P), então ela é a solução ótima de (P).
A forma de relaxação mais freqüentemente utilizada em
problemas MILP é tornar as variáveis binárias em
variáveis contínuas:
0y1
gerando um problema LP relaxado.
Outra forma de relaxação é remoção de algumas
restrições de (P). Porém, existe um compromisso entre
a relaxação e a qualidade do limite inferior (zRP) para a
solução ótima.
Em geral, quanto mais fácil for a solução do problema
relaxado (maior relaxamento), maior será a diferença
entre zRP e zP.
Sondagem
Seja (CS) um subproblema candidato para a solução de (P). Desejase então determinar se a região viável de (CS), FS(CS), contém uma
solução ótima de (P), para então encontrá-la.
Este subproblema (CS) será considerado sondado se uma das
seguintes condições for satisfeita:
(i)
estiver garantido que FS(CS) não pode conter uma solução
melhor que a melhor solução já encontrada em estágios
anteriores (ou solução titular, z*). Se nenhuma solução viável
havia sido encontrada, então z* = ;
(ii) uma solução ótima de (CS) foi encontrada, zCS
Em qualquer uma destas situações o subproblema (CS) não necessita
de novas separações.
Denotando por (RCS) uma relaxação do subproblema (CS), e zRCS a
sua solução ótima, então os critérios gerais de sondagem em um
algoritmo de branch and bound, baseado em relaxação, são:
a) Se (RCS) não possui solução viável, então (CS) também não possui
e pode ser considerado sondado;
b) Se zRCS  z* então (CS) está sondado;
c) Se uma solução ótima de (RCS) é viável para (CS), então ela é
também uma solução ótima de (CS), portanto o problema (CS) pode
ser considerado sondado. Neste caso, a solução também é viável
para (P) e se zRCS < z*, então a solução titular é substituída por
esta nova solução, senão zRCS é um limite superior para o problema
Note que é possível ter
zCS  z* > zRCS
e neste caso (CS) não pode ser considerado sondado,
sendo zRCS um limite inferior para o problema.
Portanto, quanto menor a diferença entre a solução do
problema (RCS) e o problema (CS), mais freqüentemente
estes critérios serão utilizados para eliminar ramificações.
O sucesso dos algoritmos de branch and bound está
baseado no percentual de eliminação de subproblemas e
no esforço requerido para resolver os subproblemas
candidatos.
Um algoritmo genérico para os métodos de branch and bound:
1) Inicializar a lista de subproblemas (CS) = (P), ou árvore binária, z* = ;
2) Se a lista de subproblemas (CS) estiver vazia, então FIM (se z* = ,
então não existe solução viável);
3) Selecionar um candidato da lista, tornado-o candidato (CS) corrente;
4) Selecionar e resolver uma relaxação (RCS) do (CS) corrente, obtendo a
solução zRCS;
5) Aplicar os três critérios de sondagem:
a) Se (RCS) é inviável, então o (CS) corrente não tem solução viável
e (ir para 2);
b) Se zRCS  z*, então o (CS) corrente não tem solução viável melhor
que z* e (ir para 2);
c) Se a solução ótima de (RCS) é viável para (CS) e zRCS < z*, então
z*  zRCS e (ir para 2);
6) Separar o (CS) corrente e adicionar os seus subproblemas filhos na
lista de subproblemas (CS). (ir para 2).
Existem três alternativas principais para selecionar os
candidatos da árvore binária:
1. Busca em primeira profundidade (depth-first search) com
retrocesso (LIFO: Last-In-First-Out). Técnica padrão da maioria
dos algoritmos;
2. Busca em primeira largura (breadth-first search);
3. Busca pelo melhor limite.
Exemplo: Para ilustrar o método de branch and bound com relaxação
das variáveis binárias, seja o seguinte problema:
onde a solução ótima ocorre no ponto x* = 0 e y* = [1 0 1]T, com o valor
da função objetivo S(x*,y*) = z* = 6.
raiz
nível 0
nível 1
nível 2
nível 3
Busca em primeira profundidade
Busca em primeira largura