Aula 23: Geração de colunas - Otimização Linear e Inteira · Algoritmo de geração implícita de colunas 1 Resolver o Programa Linear LP(J) (chamado Problema Mestre): min: X

Aula 23: Geração de colunasOtimização Linear e Inteira

Túlio Toffolohttp://www.toffolo.com.br

BCC464 / PCC174 – 2018/2Departamento de Computação – UFOP

http://www.toffolo.com.br

Aula de Hoje

1 Geração de Colunas

2 Exemplo: Problema de Corte Unidimensional

3 Como implementar?

4 Decomposição de Dantzig-Wolfe

5 Exemplo: Time Constrained Shortest Path

1 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 23: Geração de colunas

Aula de Hoje



3 Como implementar?




Funcionamento do algoritmo

Problema Mestre

Geração de Colunas(subproblemas)

co

luna

s


Algoritmo de geração implícita de colunas

1 Resolver o Programa Linear LP (J) (chamado Problema Mestre):

min.∑j∈J

cjxj

s.a. Ax ≥ bx ≥ 0

2 Pricing: considerando o valor das variáveis duais π, descubra seexiste alguma variável j /∈ J com custo reduzido negativo, ou seja,uma variável j /∈ J tal que cj − πAj < 0.

Se existir, insira a nova variável em LP (J) e retorne ao passo 1.

Caso contrário, a solução é ótima para todas as variáveis!


Aula de Hoje



3 Como implementar?




Sub-problemas de “Pricing”

Chamamos de Pricing os subproblemas que resolvemos paraencontrar as variáveis com custo reduzido negativo (para problemasde minimização).

Como seria o pricing no caso do Problema de Corte Unidimensional?

O pricing consistirá em gerar um ou mais padrões de corte comcusto reduzido negativo.

Para encontrar este(s) padrão(ões), resolvemos um problema deotimização!

Mas... qual problema?


Exemplo: Problema de Corte Unidimensional

Problema Mestre

min.∑p∈P

λp

s.a.∑p∈P

ai,pλp≥ bi ∀i ∈ {1, . . .m}

λp ≥ 0

Como avaliar o custo reduzido de um novo padrão p?

Utilizamos os valores duais π das restrições!

Lembre-se que o valor dual πi de uma restrição i indica o ganhoque obtemos ao alterar o RHS desta restrição...

Utilizaremos π para calcular o benefício de adicionar uma variável pcom coeficiente ai,p em cada restrição i.



Problema Mestre

min.∑p∈P

λp

s.a.∑p∈P

ai,pλp≥ bi ∀i ∈ {1, . . .m}

λp ≥ 0

No exemplo acima, um padrão p terá custo reduzido c̄p negativo se:

c̄p = 1−m∑i=1

πiaip < 0

Assim, queremos encontrar um padrão viável que minimize c̄p.



Problema Mestre

min.∑p∈P

λp

s.a.∑p∈P

ai,pλp≥ bi ∀i ∈ {1, . . .m}

λp ≥ 0

Pricing

min. 1−m∑i=1

πiai

s.a.

m∑i=1

wiai ≤ L; ai ∈ Z+ ∀i ∈ {1, . . .m}



Vamos resolver uma instância do problema:

Estoque Pedidos (m = 4)n = 10L = 250

w = [ 187, 119, 74, 90 ]b = [ 1, 2, 2, 1 ]

n: número de barras disponíveis

L: tamanho das barras

m: número de diferentes peças

w: tamanhos das peças solicitadas

b: quantidade requisitada de cada peça.


Primeiro passo: mestre deve ser factível

Precisamos de uma solução inicial (ou utilizar variáveis artificiais):

O mestre restrito deve ter solução factível

Do contrário, como obteremos valores duais?

Podemos, por exemplo, gerar uma solução trivial...

Exemplo de padrões de corte iniciais:

Padrão 1: cortar uma unidade do item 1





Mestre restrito inicial

1a iteração: mestre com os quatro padrões de corte iniciais

min. z = λ1+λ2+λ3+λ4

s.a. λ1 ≥ 1 (π1)

λ2 ≥ 2 (π2)

λ3 ≥ 2 (π3)

λ4 ≥ 1 (π4)

Solução do mestre:

z = 6 e λ1 = 1, λ2 = 2, λ3 = 2, λ4 = 1

Shadow prices (valores duais):

π1 = 1, π2 = 1, π3 = 1, π4 = 1, ou seja: π = [ 1 1 1 1 ]


Pricing

Formulação do problema de pricing (encontrar padrões de corte comcusto reduzido negativo considerando valores duais π):

min. c̄ = 1−m∑i=1

πiai

s.a.

m∑i=1

wiai ≤ L

ai ∈ Z+ ∀i ∈ Z+

Substituindo os valores de π e w, teremos:


Pricing

1a iteração: π = [ 1 1 1 1 ], portanto:

min. c̄ = 1 −a1 −a2 −a3 −a4s.a. 187a1 +119a2 +74a3 +90a4 ≤ 250

a1, a2, a3, a4 ∈ Z+

Solução ótima do pricing:

c̄ = −2

a = [ 0 0 3 0 ]

Novo padrão gerado:

Coluna 5 (representada por λ5): cortar 3 vezes o item 3


Mestre restrito

2a iteração:

min. z = λ1+λ2+λ3+λ4 +λ5

s.a. λ1 ≥ 1 (π1)

λ2 ≥ 2 (π2)

λ3 +3λ5 ≥ 2 (π3)

λ4 ≥ 1 (π4)


z = 143 e λ1 = 1, λ2 = 2, λ4 = 1, λ5 = 2

3


π =[

1 1 13 1]


Pricing

2a iteração: π =[

1 1 13 1], portanto:

min. c̄ = 1 −a1 −a2 −1

3a3 −a4

s.a. 187a1 +119a2 +74a3 +90a4 ≤ 250

a1, a2, a3, a4 ∈ Z+


c̄ = −1

a = [ 0 0 0 2 ]




Mestre restrito

3a iteração:

min. z = λ1+λ2+λ3+λ4 +λ5 +λ6

s.a. λ1 ≥ 1 (π1)

λ2 ≥ 2 (π2)

λ3 +3λ5 ≥ 2 (π3)

λ4 +2λ6 ≥ 1 (π4)


z = 256 e λ1 = 1, λ2 = 2, λ5 = 2

3 , λ6 = 12


π =[

1 1 13

12

]13 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 23: Geração de colunas

Pricing

3a iteração: π = [ 1 1 13

12 ], portanto:

min. c̄ = 1 −a1 −a2 −1

3a3 −

1

2a4

s.a. 187a1 +119a2 +74a3 +90a4 ≤ 250

a1, a2, a3, a4 ∈ Z+


c̄ = −1

a = [ 0 2 0 0 ]




Mestre restrito

4a iteração

min. z = λ1+λ2+λ3+λ4 +λ5 +λ6 +λ7

s.a. λ1 ≥ 1 (π1)

λ2 +2λ7 ≥ 2 (π2)

λ3 +3λ5 ≥ 2 (π3)

λ4 +2λ6 ≥ 1 (π4)


z = 196 e λ1 = 1, λ5 = 2

3 , λ6 = 12 , λ7 = 1


π =[

1 12

13

12


Pricing

4a iteração: π = [ 1 12

13

12 ], portanto:

min. c̄ = 1 −a1 −1

2a2 −

1

3a3 −

1

2a4

s.a. 187a1 +119a2 +74a3 +90a4 ≤ 250

a1, a2, a3, a4 ∈ Z+


c̄ = −16

a = [ 0 0 2 1 ]


Coluna 8 (λ8): cortar 2 vezes o item 3 e uma vez o item 4


Mestre restrito

5a iteração:

min. z = λ1+λ2+λ3+λ4 +λ5 +λ6 +λ7 +λ8

s.a. λ1 ≥ 1 (π1)

λ2 +2λ7 ≥ 2 (π2)

λ3 +3λ5 +2λ8 ≥ 2 (π3)

λ4 +2λ6 +λ8 ≥ 1 (π4)


z = 3 e λ1 = 1, λ7 = 1, λ8 = 1


π =[

1 12

14

12


Pricing

5a iteração: π = [ 1 12

14

12 ], portanto:

min. c̄ = 1 −a1 −1

2a2 −

1

4a3 −

1

2a4

s.a. 187a1 +119a2 +74a3 +90a4 ≤ 250

a1, a2, a3, a4 ∈ Z+


c̄ = 0

a = [ 0 0 2 1 ]

Como o custo reduzido é maior ou igual a zero......

Encontramos a solução ótima do mestre!


Aula de Hoje



3 Como implementar?




Geração de colunas

Embora baseado em uma idéia simples, a implementação de umalgoritmo de geração de colunas não é trivial.Alguns desafios:

Solução inicial (ou usar variáveis artificiais?)

Possíveis dificuldades numéricas

Definição de parâmetros. Exemplos:

Quantas colunas adicionar por iteração?

Quanta energia dedicar para encontrar a melhor coluna?

Métodos heurísticos × exatos.


Aula de Hoje



3 Como implementar?




Decomposição de Dantzig-Wolfe

Uso comum de geração de colunas: separar o conjunto de restrições“fáceis” do resto das restrições do problema (as restrições“complicadoras”)

As restrições fáceis podem envolver uma pequena porção dasvariáveis do problema

Essas restrições podem apresentar uma estrutura especial, como ade algum problema em grafos para o qual existam algoritmosrápidos de resolução

Assim, pode-se resolver separadamente as restrições fáceis!



Alguns modelos possuem uma certa estrutura...

min cx

s.a. Ax ≥ bDx ≥ dx ∈ Zn

Em alguns casos, esta estrutura significa: subproblemas fáceis ouconhecidos

Podemos explorar esta estrutura para reformular o problema, obtendogeralmente um modelo mais forte


Estrutura clássica para DW

min cx

s.a. Ax ≥ bDx ≥ dx ∈ Z+

Em caso de Programas Inteiros, a decomposição de Dantzig-Wolferesulta em uma convexificação parcial: conv{x ∈ Zn|Dx ≥ d}


Estrutura clássica para DW

min cx

s.a. Ax ≥ bDx ≥ dx ∈ Z+

Em caso de Programas Inteiros, a decomposição de Dantzig-Wolferesulta em uma convexificação parcial: conv{x ∈ Zn|Dx ≥ d}


Aula de Hoje



3 Como implementar?





Exemplo: Time Constrained Shortest Path

Fonte: Desrosiers and Lübbecke (2005)Column Generation – Chapter 1: A Primer in Column Generationhttp://www.or.rwth-aachen.de/research/publications/primer.pdf

O problema é descrito por um grafo G = (V,A)

A arco (i, j) ∈ A é associado um custo ci,j e uma duração ti,j

Deve-se encontrar o menor caminho entre os vértices v1 e vn

Sujeito a restrições adicionais de capacidade (tempo total da rota)

Problema é NP-difícil-fraco (admite algoritmo pseudopolinomial)

Portanto, uso de Programação Inteira é justificado


http://www.or.rwth-aachen.de/research/publications/primer.pdf




Example: Taken from the “Primer”

Find: Resource constrained shortest path from 1 to 6Total traversal time must not exceed 14 units

3 5

42

6

(2,3)

(10,1)

(2,2)

(12,3)

(1,7)

(1,1)

(1,2)

(1,10)

(10,3)

1

(5,7)

@mluebbecke · #colgen2018 · The Basics · 27/128

custotempo

Suponha que a rota não pode ultrapassar 14 unidades de tempo








42

6

(2,3)

(10,1)

(2,2)

(12,3)

(1,7)

(1,1)

(1,2)

(1,10)

(10,3)

1

(5,7)

3 5

Path 1-3-5-6 is quick but expensive: cost 24, time 8


custotempo

Caminho mais rápido é caro: custo 24 | 8 unidades de tempo








42

6

(2,3)

(10,1)

(2,2)

(12,3)

(1,7)

(1,1)

(1,2)

(1,10)

(10,3)

1

(5,7)

3 5

Path 1-2-4-6 is cheap but too slow: cost 3, time 18


tempocusto

Caminho mais barato demora: custo 3 | 18 unidades de tempo








3 5

42

6

(2,3)

(10,1)

(2,2)

(12,3)

(1,7)

(1,1)

(1,2)

(1,10)

(10,3)

1

(5,7)

Path 1-3-2-4-6 is optimal: cost 13, time 13


custotempo

Caminho ótimo: custo 13 | 13 unidades de tempo




Seja ci,j o custo do arco (i, j), ti,j o tempo para percorrer o arco (i, j)e T = 14 o tempo total disponível para o percurso:

min∑

(i,j)∈A

ci,jxi,j

s.a.∑

j:(i,j)∈A

xi,j −∑

j:(j,i)∈A

xi,j =

+1 se i é a origem (i = 1)

−1 se i é o destino (i = 6)

0 caso contrário,

∀v ∈ V

∑(i,j)∈A

ti,jxi,j ≤ T

xi,j ∈ {0, 1} ∀(i, j) ∈ A

Como decompor o problema?

Exploramos o subproblema de caminho mínimo!



Se retirarmos a restrição de capacidade, temos um modelo cuja matrixde coeficientes é TUM (Totalmente Unimodular).

min∑

(i,j)∈A

ci,jxi,j

s.a.∑

j:(i,j)∈A

xi,j −∑

j:(j,i)∈A

xi,j =



0 caso contrário,

∀v ∈ V

xi,j ∈ {0, 1} ∀(i, j) ∈ A

É simples verificar esta propriedade!



Aprendemos anteriormente que uma matrix A é TUM se:1 A contém apenas valores −1, 0 e +1 tal que haja no máximo dois

valores não-nulos em cada coluna.

e existe uma partição R1 e R2 de suas linhas (R) tais que:1 Cada coluna com dois termos não nulos de mesmo sinal tem uma

entrada em R1 e outra em R2.2 Cada coluna com dois termos não nulos de sinal diferente tem ambas

entradas em R1 ou em R2.

No exemplo, claramente cada coluna tem exatamente 2 termos não nulosde sinais diferente!

Assim, uma partição R1 = R e R2 = ∅ satisfaz as condições.



Podemos utilizar caminhos ao invés de arcos!

xi,j =∑p∈P

xp,i,jλp ∀(i, j) ∈ A∑p∈P

λp = 1

λp ≥ 0 ∀p ∈ P

P é o conjunto de todos os caminhos do nó 1 ao 6

xp,i,j = 1 se o arco (i, j) está no caminho p e 0 caso contrário∑p∈P

λp = 1 é chamada de restrição de convexificação



Agora vamos substituir xi,j no problema original:

min∑p∈P

∑(i,j)∈A

ci,jxp,i,jλp

s.a.∑p∈P

∑(i,j)∈A

ti,jxp,i,jλp ≤ T

xi,j =∑p∈P

xp,i,jλp ∀(i, j) ∈ A

∑p∈P

λp = 1

λp ≥ 0 ∀p ∈ P

xi,j ∈ Z+ ∀(i, j) ∈ A

Relaxando a integralidade, podemos remover o link entre xi,j e xp,i,j .



Após remover o link entre xi,j e xp,i,j , obtemos a formulação a seguir:

min∑p∈P

∑(i,j)∈A

ci,jxp,i,jλp

s.a.∑p∈P

∑(i,j)∈A

ti,jxp,i,jλp ≤ T∑p∈P

λp = 1

λp ≥ 0 ∀p ∈ P

Problema: o número de caminhos é exponencial...

Resolvemos este modelo por meio de geração de colunas.



Problema Mestre

min∑p∈P

∑(i,j)∈A

ci,jxp,i,jλp

s.a.∑p∈P

∑(i,j)∈A

ti,jxp,i,jλp ≤ T (π)

∑p∈P

λp = 1 (τ)

λp ≥ 0 ∀p ∈ P

PricingEncontre um caminho p tal que:

c̄p =∑

(i,j)∈A

ci,jxp,i,j −∑

(i,j)∈A

ti,jxp,i,jπ − τ < 0



Para encontrar a coluna com menor custo reduzido resolvemos:

Pricing – Problema de Otimização

min c̄ =∑

(i,j)∈A

ci,jxi,j −∑

(i,j)∈A

ti,jxi,jπ − τ

s.a.∑

j:(i,j)∈A

xi,j −∑

j:(j,i)∈A

xi,j =



0 caso contrário,

∀v ∈ V

xi,j ∈ {0, 1} ∀(i, j) ∈ A

Se c̄ ≥ 0, não há variáveis que melhorem a solução!

Caso contrário, encontramos uma variável (coluna) que deve seradicionada.



Eis o problema de caminho mínimo referente ao Pricing:

Pricing Subproblem

In our case this is a shortest path problem in

5

61

2

3

4

10 − 1π

10 − 3π

1 − 2π

1 − 10π

1 − 1π

1 − 7π1

2 − 2π

12 − 3π

2 − 3π

5 − 7π

This is the original graph with modified costs


Note que os custos das arestas incluem o valor dual π.

Neste exemplo, o valor dual da restrição de convexificação (τ ) adicionauma constante na função objetivo.


/ 12

Perguntas?

Documents

Aula 23: Geração de colunas - Otimização Linear e Inteira · Algoritmo de geração implícita de colunas 1 Resolver o Programa Linear LP(J) (chamado Problema Mestre): min: X