26
Otimiza¸ ao de Grande Porte Alexandre Salles da Cunha DCC-UFMG, Maio 2010 Alexandre Salles da Cunha Otimiza¸c˜ ao de Grande Porte

[Robson] 6. Otimização de Grande Porte

  • Upload
    lapodcc

  • View
    407

  • Download
    1

Embed Size (px)

Citation preview

Page 1: [Robson] 6. Otimização de Grande Porte

Otimizacao de Grande Porte

Alexandre Salles da Cunha

DCC-UFMG, Maio 2010

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 2: [Robson] 6. Otimização de Grande Porte

Escopo do Capıtulo

Geracao de Colunas

Princıpio de Decomposicao de Dantzig-Wolfe

Aplicacao em do Princıpio em PL

Aplicacao de CG e DW em Programacao Inteira

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 3: [Robson] 6. Otimização de Grande Porte

O Problema de Cortes Unidimensional

Dados do problema:

Uma quantidade irrestrita (tao grande quanto queiramos) de bobinasde papel de largura W e altura H.

Um conjunto de m perfis de tiras de papel.

Cada perfil possui altura H (a mesma altura da bobina) e largurawi ∈ Z+, wi ≤W .

Demandas bi ∈ Z+ associadas a cada perfil i de tiras de papel.

Objetivo

Cortar bobinas de forma a atender a demanda de cada perfil de tiras depapel, de forma que o numero de bobinas cortadas seja o menor possıvel.

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 4: [Robson] 6. Otimização de Grande Porte

Formulacao de Kantorovich (1960)

Seja K um limite superior para o numero mınimo de bobinas a seremcortadas, por exemplo, K =

∑mi ⌈

bij

Wwi

k⌉

Variaveis de decisao:◮ xk

i ∈ Z+ indicando quantos perfils i sao cortados na k−esima bobina.◮ yk ∈ B assumindo valor 1 caso a k−esima bobina seja usada (0, cc)

minK

k=1

yk (1)

K∑

k=1

xki ≥ bi ∀i (2)

m∑

i=1

wixki ≤ Wyk ∀k (3)

xkk ∈ Z+ ∀k, i (4)

y j ∈ B ∀k (5)Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 5: [Robson] 6. Otimização de Grande Porte

Formulacao de Gilmore e Gomory (1961)

Definicao - padrao de corte

Dizemos que um padrao (pattern) de corte j e um modo valido de cortar abobina de largura W se a restricao da Mochila Inteira:

m∑

i=1

aijwi ≤W

onde aij denota a quantidade de perfis do tipo i cortados no padrao j . Assobras do padrao de corte nao sao reaproveitadas.

Vamos assumir que:

P denota o conjunto de todos os possıveis padroes de corte viaveis eque |P | = n.

O vetor m dimensional de entradas inteiras Aj denota o numero deperfis de cada tipo cortados no padrao j ∈ P .

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 6: [Robson] 6. Otimização de Grande Porte

Formulacao de Gilmore e Gomory (1961)

Variavel de decisao: xj ∈ Z+ que representa o numero de vezes que operfil j ∈ P for empregado.

min

n∑

j=1

xj (6)

n∑

j=1

Ajxj = bi i = 1, . . . ,m (7)

xj ∈ Z j = 1, . . . , n (8)

Esta formulacao compreende m restricoes e um numeroexponencialmente grande de variaveis de decisao (colunas).

Assim sendo e impraticavel resolver o problema atraves de um metodoque use explicitamente todas as colunas da formulacao.

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 7: [Robson] 6. Otimização de Grande Porte

Como se utiliza a formulacao anterior ?

Relaxamos a integralidade das restricoes, substituindo xj ∈ Z+ porxj ≥ 0.

Resolvemos o Problema de Programacao Linear associado, obtendo-selimites de Relaxacao Linear que serao usados em um procedimentoenumerativo do tipo Branch-and-bound (na verdade sao chamados deBranch-and-price).

Para resolver a Relaxacao Linear da formulacao, precisamos usar ascolunas implicitamente e nao explicitamente, atraves do procedimentode Geracao de Colunas.

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 8: [Robson] 6. Otimização de Grande Porte

Geracao de Colunas

Vamos considerar o PL (Master Restrito):

min∑

j∈P

xj (9)

j∈P

Ajxj = bi i = 1, . . . ,m (10)

xj ≥ 0 j ∈ P (11)

onde P ⊆ P : |P | << |P |.

Exemplo: fazemos cada padrao de P ser exatamente equivalente aocorte de um unico perfil i (|P | = m).

Vamos assumir que uma solucao basica viavel para o PL acima sejapossıvel de ser encontrada. No caso da escolha de P acima e claroque xj = bi e uma solucao basica viavel.

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 9: [Robson] 6. Otimização de Grande Porte

Geracao de Colunas

Resolvemos o Programa Linear dado pelo Master Restrito (definido apartir de P) atraves do Metodo Simplex, obtendo uma solucao basicaviavel associada a uma base B e o valor zP para o seu mınimo.

Para garantir que zP seja o valor do otimo do Programa LinearOriginal (Master), precisamos garantir que nao existam colunasatrativas nao incluıdas em P .

Para decidir sobre esta questao, precisamos verificar se existe colunaj ∈ P \ P que possua custo reduzido c j = 1− p′Aj < 0, ondep′ = c ′BB−1 e o vetor de variaveis duais otimas.

Como determinar se existe j : c j < 0 sem enumerar todas as colunas ?

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 10: [Robson] 6. Otimização de Grande Porte

Resolvendo o Problema de Precificacao

Ao inves de enumerar todas as colunas e calcular c j , formulamos umProblema de Otimizacao que nos permite decidir sobre a existencia dej : c j < 0.

Formulamos e resolvemos o Problema de Precificacao max p′Aj paratodo j (recorde que Aj = (a1j , . . . , amj)

′)

Neste caso, o Problema de Precificacao consiste no Problema daMochila Inteira:

max

m∑

i=1

piaij (12)

m∑

i=1

aijwi ≤W (13)

aij ∈ Z+ (14)

que pode ser resolvido em tempo pseudo polinomial O(mW ) atravesde Programacao Dinamica.

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 11: [Robson] 6. Otimização de Grande Porte

O Metodo de Geracao de colunas

Vamos assumir que o Problema de Precicacao tenha sido resolvido eque o perfil k ∈ P seja sua solucao otima.

Se ck = 1−∑m

i=1piaki < 0, a coluna k deve ser introduzida no

modelo. Neste caso, fazemos P ← P ∪ {k}, redefinindo um novoProblema Master Restrito, que e reotimizado e o procedimento serepete, dando origem a uma nova iteracao do Metodo de Geracao deColunas.

Caso contrario, se ck = 1−∑m

i=1piaki ≥ 0, o valor do Programa

Master Restrito corresponde a solucao otima da Relaxacao Linear doproblema de corte unidimensional. Alem disto, a solucao basica otimado Master restrito e uma solucao basica otima do Programa Master.

Podemos adotar varios criterios para descartar ou nao variaveis(colunas) em P ao longo de cada iteracao do Metodo.

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 12: [Robson] 6. Otimização de Grande Porte

Geracao de Planos de Corte

Vamos considerar o Programa Linear Master e seu Dual:

minn

j=1

xj

n∑

j=1

Ajxj = bi , i = 1, . . . ,m

xj ≥ 0 j = 1, . . . , n

maxm

i=1

pibi

m∑

i=1

piaij ,≤ cj j = 1, . . . , n

Ao inves de resolver o Dual, vamos resolver uma relaxacao para oDual, escrito em termos apenas de um conjunto P de restricoes:

max

m∑

i=1

pibi

m∑

i=1

piaij ,≤ cj j ∈ P

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 13: [Robson] 6. Otimização de Grande Porte

Geracao de Planos de Corte

Considerando que o Dual Relaxado foi resolvido e que obtivemos p∗ comosua solucao otima, temos duas possibilidades:

Caso 1 - p∗ e uma solucao viavel para o problema dual original. Nestecaso, p∗ tambem e solucao otima para o problema dual original,porque qualquer solucao p deste e viavel para o relaxado e entao:p′b ≤ (p∗)′b.

Caso 2 - p∗ e inviavel para o problema dual original. Neste caso,existe uma restricao dual violada por p∗. Identificamos esta restricao,introduzimos a mesma no dual Relaxado e reotimizamos.

Para proceder com este algoritmo, precisamos resolver o Problema deSeparacao que consiste em identificar uma restricao dual violada ougarantir que restricoes violadas nao existam.

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 14: [Robson] 6. Otimização de Grande Porte

Geracao de Colunas

O Problema de Separacao

min cj − (p∗)′Aj

j ∈ P

Se o valor otimo deste Programa Linear, obtido para a restricao k, enao negativo, garantimos que p∗ e viavel para o Problema DualOriginal.

Caso contrario, se ck < (p∗)Ak para a coluna que resolveu oProblema de Separacao, introduzimos a correspondente restricao noDual Relaxado, fazendo P ← P ∪ {k}

Aplicar o algoritmo de Geracao de Colunas no Problema Primal equivale aaplicar o algoritmo de Geracao de Planos de Cortes no seu dual.

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 15: [Robson] 6. Otimização de Grande Porte

Geometria do algoritmo de Geracao de Planos de Corte

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 16: [Robson] 6. Otimização de Grande Porte

Decomposicao de Dantzig-Wolfe

Vamos considerar o seguinte Programa Linear com estrutura:

min c ′1x1 + c ′2x2

D1x1 + D2x2 = b0

F1x1 = b1

F2x2 = b2

x1, x2 ≥ 0

onde x1, x2, b0, b1, b2 sao vetores de dimensoes n1, n2,m0,m1,m2,respectivamente e as matrizes D1,D2,F1,F2 possuem dimensoesapropriadas.

Observe que:

as primeiras m0 restricoes fazem o acoplamento dos vetores x1, x2

os sistemas F1x1 = b1,F2x2 = b2 sao independentes de x2, x1

respectivamente.Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 17: [Robson] 6. Otimização de Grande Porte

Reformulando o Problema

Vamos considerar os seguintes poliedros:

Pi = {xi ∈ Rni+ : Fixi = bi}

e assumir que Pi : i = 1, 2 sao nao vazios.

Podemos entao reescrever o Programa Linear da seguinte forma:

min c ′1x1 + c ′2x2

D1x1 + D2x2 = b0

x1 ∈ P1

x2 ∈ P2

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 18: [Robson] 6. Otimização de Grande Porte

Reformulando o Problema

Vamos considerar entao que {x ji : j ∈ Ji} denota o conjunto de

pontos extremos do poliedro Pi : i = 1, 2.

De modo similar, vamos considerar que {wki : k ∈ Ki} denota o

conjunto de raios extremos de Pi : i = 1, 2.

Observe entao que pelo Teorema de Minkowski, um ponto qualquerxi ∈ Pi : i = 1, 2 pode ser escrito como:

xi =∑

j∈Ji

λjix

ji +

k∈Ki

θki wk

i

j∈Ji

λji = 1

λji ≥ 0, j ∈ Ji

θki ≥ 0, k ∈ Ki

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 19: [Robson] 6. Otimização de Grande Porte

Reformulando o Problema

Problema Master:

min∑

j∈J1

λj1c ′1x

j1+

k∈K1θk1c ′1w

k1 +

j∈J2

λj2c ′2x

j2+

k∈K2

θk2c ′2w

k2

j∈J1

λj1D1x

j1+

k∈K1θk1D1w

k1 +

j∈J2

λj2D2x

j2+

k∈K2

θk2D2w

k2 = b0

j∈J1

λj1

= 1

j∈J2

λj2

= 1

λji ≥ 0 j ∈ Ji , i = 1, 2

θki ≥ 0 k ∈ Ki , i = 1, 2

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 20: [Robson] 6. Otimização de Grande Porte

Reformulando o problema

Na forma matricial, o conjunto de restricoes do Problema Master fica:

X

j∈J1

λj1

2

4

D1xj1

1

0

3

5 +X

j∈J2

λj2

2

4

D2xj2

0

1

3

5 +X

k∈K1

θk1

2

4

D1wk1

0

0

3

5 +X

k∈K2

θk2

2

4

D2wk2

0

0

3

5 =

2

4

b0

1

1

3

5

Observe que, diferentemente do Programa Linear Original que possuiam0 + m1 + m2 restricoes, o Programa Reformulado possui apenasm0 + 2 linhas.

Uma base para este programa deve envolver ter dimensao m0 + 2.

Por outro lado, o novo programa possui |J1|+ |J2|+ |K1|+ |K2|variaveis.

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 21: [Robson] 6. Otimização de Grande Porte

O algoritmo de Decomposicao

Vamos assumir que dispomos de um conjunto de colunas inicial, isto e,subconjuntos J1, J2,K 1,K 2 que nos permita resolver e obter uma solucaobasica viavel para o Programa Master Restrito:

min∑

j∈J1

λj1c ′1x

j1+

k∈K 1θk1c ′1w

k1 +

j∈J2

λj2c ′2x

j2+

k∈K 2

θk2c ′2w

k2

j∈J1

λj1D1x

j1+

k∈K 1θk1D1w

k1 +

j∈J2

λj2D2x

j2+

k∈K 2

θk2D2w

k2 = b0

j∈J1

λj1

= 1

j∈J2

λj2

= 1

λji ≥ 0 j ∈ J i , i = 1, 2

θki ≥ 0 k ∈ K i , i = 1, 2

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 22: [Robson] 6. Otimização de Grande Porte

O algoritmo de Decomposicao

Assumimos entao que B denote a matriz basica associada aoPrograma Master Restrito, resolvido a otimalidade.

Seja p′ = c ′BB−1 o vetor m0 + 2 dimensional de variaveis duaisotimas, do Programa Dual do Master Restrito.

Vamos dizer que p = (q, r1, r2), onde r1 e r2 sao as variaveis duaisassociadas as restricoes de convexidade.

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 23: [Robson] 6. Otimização de Grande Porte

O algoritmo de Decomposicao

Custos reduzidos

Os custos reduzidos de uma variavel λj1

sao dados por

c ′1xj1−

[

q′ r1 r2]

D1xj1

10

= (c ′1 − q′D1)xj1− r1

Os custos reduzidos de uma variavel θk1

sao dados por

c ′1wj1−

[

q′ r1 r2]

D1wj1

00

= (c ′1 − q′D1)wj1

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 24: [Robson] 6. Otimização de Grande Porte

O algoritmo de Decomposicao

Custos reduzidos

Os custos reduzidos de uma variavel λj2

sao dados por

c ′2xj2−

[

q′ r1 r2]

D2xj2

01

= (c ′2 − q′D2)xj2− r2

Os custos reduzidos de uma variavel θk2

sao dados por

c ′2wj2−

[

q′ r1 r2]

D2wj1

00

= (c ′2 − q′D2)wj2

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 25: [Robson] 6. Otimização de Grande Porte

Problema de Precificacao - para P1 (P2 analogo)

min (c ′1 − q′D1)x1

x1 ∈ P1

Se o problema acima for ilimitado (custo = −∞), o Metodo Simplexnos fornece um raio extremo wk

1 que satisfaz (c ′1 − q′D2)wk1 < 0.

Neste caso, inserirmos a coluna

D1wk1

00

no master restrito

(associada a variavel θk1 ) e reotimizamos usando o primal Simplex.

Se o problema possui otimo finito, atingido por xj1, de forma que

(c1 − q′D1)xj1≥ r1, a solucao do Programa Master Reduzido resolve o

Programa Master. Caso (c1 − q′D1)xj1

< r1, uma coluna com custo

reduzido negativo foi encontrado. Introduzimos a coluna

D1xk1

10

e

reotimizamos.

Alexandre Salles da Cunha Otimizacao de Grande Porte

Page 26: [Robson] 6. Otimização de Grande Porte

Inicializacao do Algoritmo

Precisamos encontrar uma solucao basica inicial para o ProgramaMaster.Para tanto, aplicamos o Simplex Fase I para cada um dossubproblemas Pi , separadamente. Com o simplex Fase I, obtemos ospontos extremos x1

1 e x12 de P1 e P2.

Construimos o Master Auxiliar e resolvemos o Simplex Fase I paraobter solucao basica para o Master Original.

min

m0∑

t=1

yt

i=1,2

j∈Ji

λjiDix

ji +

k∈Ki

θki Diw

ki

+ y = b0

j∈Ji

λji = 1, i = 1, 2

λji ≥ 0, θk

i ≥ 0, yt ≥ 0, ∀i , k, j , tAlexandre Salles da Cunha Otimizacao de Grande Porte