AULA COMPUTACIONALAULA COMPUTACIONAL

- Síntese de Sistemas de Separação Síntese de Sistemas de Separação (Cap. 7)(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

qql yyyyzz 1

321 242

2log

logint1

lu zzq

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:

onde q é o número mínimo de variáveis 01 necessárias para representar z. Este número mínimo é dado por:

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).

(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.

Então o conjunto de subproblemas (P1), (P2), ..., (Pn) de (P) é uma separação de (P) se:

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):

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).

Relaxação

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). Deseja-se 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.

nível 0

nível 2

nível 3

nível 1

raiz

Busca em primeira profundidade Busca em primeira largura