Otimização Combinatória - Parte 5

Graduação em Matemática Industrial

Otimização Combinatória - Parte 5

Prof. Thiago Alves de QueirozDepartamento de Matemática - CAC/UFG

2/2014

Thiago Queiroz (DM) Parte 5 2/2014 1 / 1

Algoritmo de Planos de Corte de Gomory

Algoritmos de planos de corte buscam obter uma aproximação daenvoltório convexa:

I A envoltória deve conter um ponto extremo correspondente asolução ótima.

A aproximação é obtida por meio de cortes ou desigualdadesválidas;Definição 3.5. Uma desigualdade φx ≤ φ0 é uma desigualdadeválida para X ⊂ Rn, se φx ≤ φ0 para todo x ∈ X ;Ou seja, uma desigualdade é válida se o conjunto X situa-se emum dos semi-espaços definidos pelo hiperplano φx = φ0.


Algoritmo de Planos de Corte de Gomory

Proposição 3.2. A desigualdade x ≤ bbc é válida paraX = {x ∈ Z 1|x ≤ b};Seja o conjunto X = {x : Ax ≤ b, x ∈ Z n

+}, em que Am×n é umamatriz com colunas {a1, . . . ,an} e seja um u ∈ Rm

+ ;A construção de uma desigualdade válida para X , conhecidocomo procedimento de Chavátal-Gomory é:

I A desigualdade∑n

j=1 uT ajxj ≤ uT b é válida para X , pois u ≥ 0 e∑nj=1 ajxj ≤ b;

I A desigualdade∑n

j=1buT ajcxj ≤ uT b é válida para X , pois x ≥ 0;I A desigualdade

∑nj=1buT ajcxj ≤ buT bc é válida para X , pois x é

inteiro, portanto∑n

j=1buT ajcxj é inteiro.

Pode-se demonstrar que toda desigualdade válida para X podeser obtida pelo procedimento acima através de um número finitode passos.


Exemplo...

Exemplo. Identifique uma desigualdade para cortar o pontox = (0,0,0, 35

6 ) do conjuntoX = {x ∈ Z 4

+ : 5x1 + 7x2 + 4x3 + 6x4 ≤ 35}.Seguindo o procedimento de Chavátal-Gomory, o primeiro passoé encontrar u ≥ 0 que mantém a desigualdade válida;Note que podemos considerar u = 1

6 :56x1 +

76x2 +

46x3 + x4 ≤ 35

6 , que resulta ao substituirx = (0,0,0, 35

6 ), resulta em:366 ≤

3636 .

Segue pelo procedimento que: b56cx1 + b7

6cx2 + b46cx3 + x4 ≤ b35

6 c,que resulta em: x2 + x4 ≤ 5,como desigualdade válida que corta o ponto x = (0,0,0, 35

6 ).


Corte de Gomory

Seja uma restrição qualquer do problema de otimização inteira:∑nj=1 ajxj ≤ b (1);

Seja a desigualdade oriunda do procedimento deChavátal-Gomory aplicado sobre esta restrição:∑n

j=1bajcxj ≤ bbc;O corte de Gomory consiste em subtrair (1) de (2), obtendo aseguinte desigualdade válida para o problema:∑n

j=1(bajc − aj)xj ≤ (bbc − b);Adicionando uma variável de folga s ≥ 0 na desigualdade, tem-se:∑n

j=1(bajc − aj)xj + s = (bbc − b);Note que o corte, ou seja, a desigualdade válida, é uma novarestrição para o problema de otimização inteira.


Corte de Gomory

O corte de Gomory é aplicado observando a tabela simplex ótima;Escolhe-se uma linha (restrição) dessa tabela cuja variável básicaassociada tem valor não inteiro;O corte deve ser inserido nesta tabela simplex ótima:

I Cria-se uma nova linha no final da tabela;I A variável básica associada a linha é a variável de folga do corte,

isto é, s ≥ 0;I Cria-se também uma nova coluna na tabela, associada a variável

de folga s;I Isto resultará em uma nova tabela simplex.

A nova tabela simplex deve ser otimizada com o algoritmo dualsimplex, pois houve a inserção de uma restrição no problema;O procedimento é repetido enquanto existir uma variável básicacom valor não inteiro.


O Algoritmo de Planos de Corte

Passo 1. (Inicialização) Faça k = 0 e seja PL0 a relaxação lineardo problema de programação inteira P;Passo 2. (Reotimização) Encontre a solução ótima de PLk ,consequentemente, sua tabela simplex ótima;Passo 3. (Otimalidade) Se a solução ótima de PLk for inteira:PARE! Solução ótima para P;Passo 4. (Corte) Escolha uma linha da tabela ótima cuja variávelé não inteira:

I Para a restrição que representa a linha da variável básicaescolhida, gere o corte:∑n

j=1(bajc − aj)xj ≤ (bbc − b);I Insira este corte no fim da tabela simplex ótima de PLk ;I Faça k = k + 1;I Vá para o Passo 2.


O Algoritmo de Planos de Corte

Observe que PL0 será resolvido pelo método simplex (emtabelas);A partir da inserção de um corte, os demais problemas linearesserão resolvidos pelo método dual simplex;Uma maneira de agilizar o algoritmo é escolher no Passo 4 avariável com parte fracionária mais próximo de 1

2 ;Exemplo. Resolva o seguinte modelo de programação inteira peloalgoritmo de planos de corte;

Maximizar z = 5x1 − x2

sujeito a :

7x1 − 5x2 ≤ 133x1 + 2x2 ≤ 17x1, x2 ∈ Z+.

(1)


Exemplo...

Passo 1. Faça k = 0 e seja PL0 a relaxação linear do problema Pa ser resolvido:

(PL0) Maximizar z = 5x1 − x2

sujeito a :

7x1 − 5x2 ≤ 133x1 + 2x2 ≤ 17x1, x2 ≥ 0.

(2)

Passo 2. Para resolver PL0, coloque-o inicialmente na formapadrão:

(PL0) Minimizar − z = −5x1 + x2 + 0x3 + 0x4

sujeito a :

7x1 − 5x2 + x3 = 133x1 + 2x2 + x4 = 17x1, x2, x3, x4 ≥ 0.

(3)


Exemplo...

A tabela simplex inicial do problema na forma padrão fica:

Tabela : Tabela simplex inicial com dados do problema primal.

x1 x2 x3 x4 bVB -5 1 0 0 zx3 7 -5 1 0 13x4 3 2 0 1 17

Note que se pode aplicar o método simplex normalmente,resultando na seguinte tabela simplex ótima:

Tabela : Tabela simplex ótima para PL0.

x1 x2 x3 x4 bVB 0 0 13

291829 16 11

29x1 1 0 2

295

29 3 2429

x2 0 1 0 − 329

729 2 22

29


Exemplo...

A representação gráfica para PL0 está na figura abaixo;

Figura : Solução ótima de PL0.

Passo 3. A solução não é inteira: (x1, x2) = (32429 ;2

2229);

Passo 4. Escolhe-se (aleatoriamente) a linha de x1, que tem valornão inteiro na solução ótima;


Exemplo...

Cria-se o corte de Gomory:(1− 1)x1 + (0− 0)x2 + (0− 2

29)x3 + (0− 529)x4 ≤ (3− 324

29)

− 229x3 − 5

29x4 ≤ −2429 ,

−2x3 − 5x4 + s1 = −24, em que s1 ≥ 0;Insere-se o corte no fim da tabela simplex ótima de PL0;Faça k = k + 1;Passo 2. O problema PL1, pois k = 1, é o problema PL0 com ocorte de Gomory gerado no passo anterior;A tabela simplex inicial de PL1 é a tabela simplex ótima de PL0

com a adição do corte no final:

Tabela : Tabela simplex inicial para PL1.

x1 x2 x3 x4 s1 bVB 0 0 13

291829 0 16 11

29x1 1 0 2

295

29 0 3 2429

x2 0 1 − 329

729 0 2 22

29s1 0 0 −2 −5 1 −24


Exemplo...

Dada a inserção de uma restrição no problema, aplica-se ométodo dual simplex partindo da tabela simplex inicial de PL1;Aplicando o dual simplex:

I Variável que sai da base: com valor mais negativo, que é s1 = −24;I Variável que entra na base: para os coeficientes negativos na linha

de s1, o mínimo, em absoluto, entre os coeficientes da linha e orespectivo coeficiente na linha da função objetivo;

I Então, x4 entra na base e o pivotamento deve ser feito. A tabelasimplex resultante é:

Tabela : Tabela simplex para PL1 após pivotamento.

x1 x2 x3 x4 s1 bVB 0 0 1

5 0 3 35 13 2

5x1 1 0 0 0 1 3x2 0 1 − 1

5 0 1 25 1 3

5x4 0 0 2

5 1 −5 45 4 4

5

I Note que chegamos na solução ótima para o dual simplex.


Exemplo...



Passo 3. A solução não é inteira: (x1, x2, x4) = (3;135 ,4

45);

Passo 4. Escolhe-se (aleatoriamente) a linha de x4, que tem valornão inteiro na solução ótima;


Exemplo...Cria-se o corte de Gomory:(0−0)x1+(0−0)x2+(0− 2

5)x3+(1−1)x4+(−6+545)s1 ≤ (4−44

5)

−25x3 − 1

5s1 ≤ −45

−2x3 − 1s1 + s2 = −4, em que s2 ≥ 0;Insere-se o corte no fim da tabela simplex ótima de PL1;Faça k = k + 2;Passo 2. O problema PL2, pois k = 2, é o problema PL1 com ocorte gerado no passo anterior;A tabela simplex inicial de PL2 é a tabela simplex ótima de PL1

com a adição do corte no final:


x1 x2 x3 x4 s1 s2 bVB 0 0 1

5 0 3 35 0 13 2

5x1 1 0 0 0 1 0 3x2 0 1 − 1

5 0 1 25 0 1 3

5x4 0 0 2

5 1 −5 45 0 4 4

5s2 0 0 −2 0 −1 1 −4


Exemplo...

Aplica-se o método dual simplex partindo da tabela simplex inicialde PL2:

I Variável que sai da base: com valor mais negativo, que é s2 = −4;I Variável que entra na base: para os coeficientes negativos na linha

de s2, o mínimo, em absoluto, entre os coeficientes da linha e orespectivo coeficiente na linha da função objetivo;

I Então, x3 entra na base e o pivotamento deve ser feito. A tabelasimplex resultante é:


x1 x2 x3 x4 s1 s2 bVB 0 0 0 0 3 1

212 13

x1 1 0 0 0 1 0 3x2 0 1 0 0 1 1

2 − 12 2

x4 0 0 0 1 −6 1 4x3 0 0 1 0 1

2 −2 12 2

I Note que chegamos na solução ótima para o dual simplex.


Exemplo...



Passo 3. A solução é inteira: (x1, x2, x3, x4) = (3,2,2,4);PARE: a solução encontrada é ótima, com (x1, x2) = (3,2) ez = 13.Thiago Queiroz (DM) Parte 5 2/2014 17 / 1

Método branch-and-cut

Este método combina as estratégias de branch-and-bound (B&B)e de planos de corte;O objetivo é reduzir o número de nós na árvore de enumeraçãoB&B;Em cada nó da árvore, adicionam-se desigualdades válidas demodo a obter um limitante mais apertado no nó;Ou seja, faz-se a inclusão de k cortes em cada nó cuja relaxaçãolinear é factível;Vale destacar que as desigualdades de Gomory foram asprimeiras propostas para problemas inteiros e inteiros mistos;O algoritmo branch-and-cut a seguir é para resolver problemas demaximização, mas pode ser facilmente adaptado para problemasde minimização;


Algoritmo branch-and-cut

Passo 0 (Inicialização). Faça z =∞, z∗ = −∞, x∗ = ∅ e L = {P};I Alguns pacotes comerciais realizam um pré-processamento no

problema P objetivando melhorar a formulação;

Passo 1 (Seleção de nó). Selecione o nó ativo i , associado aoproblema P i ∈ L e resolva a sua relaxação linear LP i . Se L estivervazia:

I Vá para o Passo 7.

Passo 2 (Teste de eliminação 1). Se a região factível de PLi forvazia:


Passo 3 (Corte). Adicione k cortes a PLi de modo a obter aformulação PLik ;

Passo 4 (Teste de eliminação 2). Se o valor z ik da solução ótimade PLik é tal que z ik ≤ z∗:



Algoritmo branch-and-cut

Passo 5 (Teste de eliminação 3). Se a solução ótima x ik de PLik éinteira com valor z ik , e se z ik > z∗:

I Faça x∗ = x ik e z∗ = z ik ;I Elimine os nós ativos i da lista L, tais que z i ≤ z∗;I Vá para o Passo 1.

Passo 6 (Ramificação). Selecione uma variável da solução ótimax ik de PLik com valor não inteiro:

I Divida P ik em dois problemas: P ik1 e P ik

2 ;I Adicione estes problemas à lista L;I Vá para o Passo 1.

Passo 7 (Fim). Se z∗ = −∞, não existe solução factível; casocontrário, a solução incumbente x∗ é uma solução ótima.


Pré-processamento

Pacotes comerciais de otimização possuem um módulo depré-processamento;Este módulo verifica a formulação original do problema:

I A meta é detectar rapidamente variáveis e restrições redundantes;I Também, apertar os limitantes das variáveis.

Se o problema resultante de programação linear/inteira émenor/mais apertado, então, possivelmente, será resolvido maisrapidamente;Isto é fundamental em problemas grandes, pois o métodobranch-and-cut pode requerer a resolução de centenas/milharesde problemas de programação linear.


Pré-processamento

Para problemas de programação linear/inteira, segue:Proposição 3.3. Considere o conjunto:S = {x : a0x0 +

∑nj=1 ajxj ≤ b, lj ≤ xj ≤ uj , j = 1, . . . ,n}.

Limitantes em variáveis. Se a0 > 0, então:

x0 ≤b−

∑{j:aj>0} aj lj−

∑{j:aj<0} aj uj

a0;

Se a0 < 0, então: x0 ≥b−

∑{j:aj>0} aj lj−

∑{j:aj<0} aj uj

a0;

Redundância. A restrição a0x0 +∑n

j=1 ajxj ≤ b é redundante se:∑{j:aj>0} ajuj +

∑{j:aj<0} aj lj ≤ b;

Infactibilidade. S = ∅ se:∑{j:aj>0} aj lj +

∑{j:aj<0} ajuj > b;


Pré-processamento

Fixação de variáveis. Para um problema de maximização naforma:max{cx : Ax ≤ b, l ≤ x ≤ u}se aij > 0, para i = 1, ldots,m e cj < 0, então faça: xj = lj ;se aij ≤ 0, para i = 1, ldots,m e cj > 0, então faça: xj = uj ;Exemplo. Aplique o pré-processamento no seguinte modelo deprogramação linear:

Maximizar z = 4x1 + 3x2 − 2x3

sujeito a :

8x1 − 5x2 + 10x3 ≤ 2010x1 + 4x2 − 2x3 ≥ 10x1 + x2 + x3 ≤ 50 ≤ x1 ≤ 3; 0 ≤ x2 ≤ 1; x3 ≥ 1.

(4)


Exemplo...

Apertando limitantes. Isolando a variável x1 na primeira restriçãoe usando os limitantes x2 ≤ 1 e −x3 ≤ −1, chega-se em:8x1 ≤ 20 + 5x2 − 10x3 ≤ 20 + 5× 1− 10× 1 = 15x1 ≤ 15

8 ;Isolando a variável x3 na primeira restrição, obtém-se:10x3 ≤ 20 + 5x2 − 8x1 ≤ 20 + 5× 1− 8× 0 = 25x3 ≤ 5

2 ;Isolando a variável x2 na primeira restrição, tem-se:5x2 ≥ 8x1 + 10x3 − 20 ≥ 8× 0 + 10× 1− 20 = −10Logo, o limitante x2 ≥ 0 não sofre mudanças;Observando agora a segunda restrição, isolando a variável x1,tem-se:10x1 ≥ 10 + 2x3 − 4x2 ≥ 10 + 2× 1− 4× 1 = 8x1 ≥ 4

5 ;A segunda e a terceira restrições não causam mudanças noslimitantes de x2 e x3 (verifique!).


Exemplo...

Com as mudanças nos limitantes das variáveis, volta-se naprimeira restrição para obter um limitante superior para x3:10x3 ≤ 20 + 5x2 − 8x1 ≤ 20 + 5× 1− 8× 4

5 = 935

x3 = 9350 ;

Restrições redundantes. Substituindo os limitantes nas restrições,vemos apenas que a terceira restrição é redundante:x1 + x2 + x3 ≤ 5158 + 1 + 93

50 ≤ 5Logo, esta restrição pode ser descartada do modelo;Até o presente, o modelo tornou-se:

Maximizar z = 4x1 + 3x2 − 2x3

sujeito a :

8x1 − 5x2 + 10x3 ≤ 2010x1 + 4x2 − 2x3 ≥ 1045 ≤ x1 ≤ 15

8 ; 0 ≤ x2 ≤ 1; 1 ≤ x3 ≤ 9350 .

(5)


Exemplo...

Fixação de variáveis. Para aplicar este procedimento, devemosobservar os coeficientes das variáveis no conjunto de restrições ena função objetivo;Partindo do modelo já melhorado, multiplicando a segundarestrição por −1, temos:8x1 − 5x2 + 10x3 ≤ 20−10x1 − 4x2 + 2x3 ≤ −10;Observando a coluna a2 de x2, note que os coeficientes sãonegativos e na função objetivo ele é positivo, segue-se, então,que:x2 = u2 = 1;Observando a coluna a3 de x3, note que os coeficientes sãopositivos e na função objetivo ele é negativo, segue-se, então,que:x3 = l3 = 1;


Exemplo...

Nada pode ser concluído sobre x1;Considerando os valores fixos de x2 = 1 e x3 = 1, o modelopassa a ser:

Maximizar z = 4x1 + 1

sujeito a :

8x1 − 5 + 10 ≤ 2010x1 + 4− 2 ≥ 1045 ≤ x1 ≤ 15

8 .

(6)

Ao substituir o limitante superior de x1 na primeira restrição, poisé de ≤, isto é, x1 = 15

8 , e o limitante inferior na segunda restrição(x1 = 4

5 ), pois é de ≥, tem-se que tais restrições são sempresatisfeitas, de forma que podem ser eliminadas;Portanto, o modelo finalmente reduz-se a:

Maximizar z = 4x1 + 1sujeito a :

{ 45 ≤ x1 ≤ 15

8 .(7)


Pré-processamento

Para problemas binários, segue:Proposição 3.4. Considere o conjunto:X = {x ∈ Bn :

∑nj=1 ajxj ≤ b}.

Infactibilidade. X = ∅ se: b < 0 e∑{j:aj<0} aj > b;

Redundância. A restrição∑n

j=1 ajxj ≤ b é redundante se:∑{j:aj>0} aj ≤ b;

Fixação de variáveis. Seja ak > 0. Se∑{j:aj<0} aj + ak > b,

então: xk = 0;Desigualdades válidas. A restrição xi + xj ≤ 1 é válida se:ai + aj > b.


Pré-processamento

Exemplo. Aplique o pré-processamento no seguinte modelo deprogramação binária:

Maximizar z = 4x1 + 3x2 − 2x3 + x4

sujeito a :

2x1 + x3 + x4 ≥ 2x1 − 2x2 + 5x3 + 2x4 ≤ 4−2x1 + 6x2 + x3 − x4 ≤ 35x2 − 3x4 ≥ 0x1, x2, x3, x4 ∈ {0,1}.

(8)

(VERIFIQUE!!!) O modelo resultante será apenas:

Maximizar z = 4 + 4x2sujeito a :

{x2 ∈ {0,1}.

(9)


Documents

Otimização Combinatória - Parte 5