Upload
lapodcc
View
407
Download
1
Embed Size (px)
Citation preview
Otimizacao de Grande Porte
Alexandre Salles da Cunha
DCC-UFMG, Maio 2010
Alexandre Salles da Cunha Otimizacao 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
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
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
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
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
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
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
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
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
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
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
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
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
Geometria do algoritmo de Geracao de Planos de Corte
Alexandre Salles da Cunha Otimizacao 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
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
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
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
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
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
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
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
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
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
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