View
3
Download
0
Category
Preview:
Citation preview
Aula 17: Planos de CorteOtimização Linear e Inteira
Túlio A. M. Toffolohttp://www.toffolo.com.br
BCC464/PCC174 –2018/2Departamento de Computação –UFOP
Previously...
Branch-and-bound em programação inteira
Desigualdades válidas
Cortes combinatórios
Exercícios
2 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Aula de Hoje
1 Caixeiro Viajante
2 Cortes Baseados em Arredondamento
3 Cortes de Gomory
3 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Caixeiro Viajante - Traveling Salesman Problem
Um vendedor precisa visitar n cidades, exatamente uma vez e entãoretornar ao seu ponto de partida.
A distância (ou o tempo esperado de locomoção) entre uma cidade i eoutra cidade j é dada por dij . Deve-se encontrar uma ordenação dascidades que permita a conclusão da viagem no menor tempo possível.
4 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Caixeiro Viajante - Formulação
Variáveis
xij =
{1 se a aresta (i, j) fará parte da rota0 caso contrário
Restrições: chega 1 vez na cidade∑i=1,...,n:i 6=j
xij = 1 ∀j = 1, . . . , n
Restrições: sai 1 vez da cidade∑j=1,...,n:j 6=i
xij = 1 ∀i = 1, . . . , n
5 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Caixeiro Viajante - Formulação
Variáveis
xij =
{1 se a aresta (i, j) fará parte da rota0 caso contrário
Restrições de Miller-Tucker-Zemlin (MTZ)
Sejam variáveis auxiliares ui ≥ 0 (i = 1, ...n):
u1 = 1
ui − uj + nxi,j ≤ n− 1 ∀i, j ∈ {2, ..., n}, i 6= j
6 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Alternativas para remover Sub-Rotas
Restrições Cut-set ∑i∈S
∑j /∈S
xij ≥ 1 ∀S ⊂ N,S 6= ∅
ou
Restrições de Eliminação de Sub-Rotas∑i∈S
∑j∈S
xij ≤ |S| − 1 ∀S ⊂ N, 2 ≤ |S| ≤ n− 1
7 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Alternativas para remover Sub-Rotas
As restrições de eliminação de sub-rotas apresentadas no último slidepodem ser incluídas por demanda:
Existe um número exponencial de restrições e, portanto, é inviávelinserir todas as restrições.
Alternativa: resolvemos o problema (violando sub-rotas) e inserimosapenas as restrições que estão sendo violadas.
Repetimos o procedimento até não haver nenhuma restrição violada.
8 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Aula de Hoje
1 Caixeiro Viajante
2 Cortes Baseados em Arredondamento
3 Cortes de Gomory
9 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Introdução
Considere o Programa Inteiro a seguir:
Maximize:k∑
j=1
cjxj
Sujeito a:k∑
j=1
aijxj ≤ bi ∀i = 1, 2, . . . ,m (1)
xj ≥ 0 ∀j = 1, 2, . . . , k (2)
xj ∈ Z ∀j = 1, 2, . . . , k (3)
10 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Cortes Baseados em Arredondamento
Cortes de Gomory
Mixed Integer Rounding
Chvátal-Gomory
11 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Exemplo de corte
Considere a restrição:2x1 + 4x2 ≤ 17 (satisfeita por x1 = 1, 7 e x2 = 3, 4).
Vamos gerar outra restrição dividindo a primeira por 2:x1 + 2x2 ≤ 8, 5
Note que do lado esquerdo temos apenas coeficientes inteiros e o valordas variáveis também deve ser inteiro. Portanto:x1 + 2x2 ≤ 8
A restrição acima denomina-se Desigualdade Válida ou Corte.Note que um corte não invalida nenhuma solução inteira válida.
12 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Cortando
1
2
3
4
1 2 3 4
Solução Inicial:x1 = 1, 67x2 = 3, 4z = 27, 11
Com o corte:x1 = 1, 8x2 = 3, 1z = 26, 4
13 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Cortando
1
2
3
4
1 2 3 4
Solução Inicial:x1 = 1, 67x2 = 3, 4z = 27, 11
Com o corte:x1 = 1, 8x2 = 3, 1z = 26, 4
13 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Cortes de Chvátal-Gomory
k∑j=1
aijxj ≤ bi ∀i = 1, 2, . . . ,m (1)
temos que:m∑i=1
ui
k∑j=1
aijxj ≤m∑i=1
uibi (2)
Desse modo, todas as soluções que satisfazem (1) e xj ≥ 0 também satisfazem:
k∑j=1
⌊m∑i=1
uiaij
⌋xj ≤
m∑i=1
uibi (3)
14 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Cortes de Chvátal-Gomory
Tendo:
k∑j=1
⌊m∑i=1
uiaij
⌋xj ≤
m∑i=1
uibi (1)
e considerando que xj ∈ Z obtemos o corte de Chvátal-Gomory :
k∑j=1
⌊m∑i=1
uiaij
⌋xj ≤
⌊m∑i=1
uibi
⌋(2)
15 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Exemplo 1
Maximize:
2x1 + x2
Sujeito a:
7x1 + x2 ≤ 28
−x1 + 3x2 ≤ 7
−8x1 − 9x2 ≤ −32x1, x2 ≥ 0
x1, x2 ∈ Z
1
2
3
4
1 2 3 4 x1
x2
16 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Exemplo 1
Restrições:
7x1 + x2 ≤ 28
−x1 + 3x2 ≤ 7
−8x1 − 9x2 ≤ −32
Quais valores de u1...u3 nosoferecem um corte em:
k∑j=1
⌊m∑i=1
uiaij
⌋xj ≤
⌊m∑i=1
uibi
⌋
u1 = 0, u2 = 13, u3 = 1
3
−3x1 − 2x2 ≤ −9
u1 = 121, u2 = 7
22, u3 = 0
x2 ≤ 3
1
2
3
4
1 2 3 4 x1
x2
17 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Exemplo 1
Restrições:
7x1 + x2 ≤ 28
−x1 + 3x2 ≤ 7
−8x1 − 9x2 ≤ −32
Quais valores de u1...u3 nosoferecem um corte em:
k∑j=1
⌊m∑i=1
uiaij
⌋xj ≤
⌊m∑i=1
uibi
⌋
u1 = 0, u2 = 13, u3 = 1
3
−3x1 − 2x2 ≤ −9
u1 = 121, u2 = 7
22, u3 = 0
x2 ≤ 3
1
2
3
4
1 2 3 4 x1
x2
17 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Exemplo 1
Restrições:
7x1 + x2 ≤ 28
−x1 + 3x2 ≤ 7
−8x1 − 9x2 ≤ −32
Quais valores de u1...u3 nosoferecem um corte em:
k∑j=1
⌊m∑i=1
uiaij
⌋xj ≤
⌊m∑i=1
uibi
⌋
u1 = 0, u2 = 13, u3 = 1
3
−3x1 − 2x2 ≤ −9
u1 = 121, u2 = 7
22, u3 = 0
x2 ≤ 3
1
2
3
4
1 2 3 4 x1
x2
17 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Exemplo 2
Seja o modelo de Programação Inteira P a seguir:
min∑j∈J
cjxj
s.t.∑j∈J
aijxj ≤ bi ∀i ∈ I
xj ∈ Z+ ∀j ∈ J
Limites inferiores fortes para P podem ser obtidos pela inclusão derestrições de Chvàtal-Gomory na relaxação linear de P :
buTAcx ≤ buT bc
18 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Exemplo 2
Considere as seguintes desigualdades:
i1 : 2x1 + 5x2 + 3x3 ≤ 3
i2 : x1 + x4 ≤ 1
i3 : 3x1 − 2x2 ≤ 2
Seja u = {0.25; 0.15; 0.5}Desta forma, temos: 2.15x1 + 0.25x2 + 0.75x3 + 0.15x4 ≤ 1.9
αx1 = 2
αx2 = 0
αx3 = 0
αx4 = 0
α0 = 1
Corte de Chvàtal-Gomory produzido: 2x1 ≤ 1
19 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Como encontrar cortes de Chvàtal-Gomory?
Fischetti e Lodi (2007) propuseram o MIP a seguir, S:
max :
n∑j=1
αjx∗j − α0
s.t. fj = uTAj − αj ∀j ∈ J∗
f0 = uT b− α0
αj ∈ Z+ ∀j ∈ J∗ ∪ {0}0 ≤ fj ≤ 1− ε ∀j ∈ J∗
0 ≤ ui ≤ 1− ε ∀i ∈ I
J∗ é o conjunto de variáveis ativas na solução fracionária
fj é a variável de folga para capturar o coeficiente fracionário
ε é a tolerância (para melhorar estabilidade numérica)
20 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
ExercíciosConsiderando as restrições anteriores:
7x1 + x2 ≤ 28
−x1 + 3x2 ≤ 7
−8x1 − 9x2 ≤ −32
1 Encontre valores de u1, u2, u3 que resultam no plano de corte:−x1 − x2 ≤ −4
2 Encontre, se existirem, valores de u1, u2, u3 que resultam nadesigualdade: −x1 ≤ −2Dica: prepare um sistema de desigualdades com as variáveis u1, u2, u3
21 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Aula de Hoje
1 Caixeiro Viajante
2 Cortes Baseados em Arredondamento
3 Cortes de Gomory
22 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Cortes de Gomory
x1 x2 x3 x4 rhs
z : 0 0 1, 25 0, 75 5, 25
r1 : 0 1 2, 25 −0, 25 2, 25
r2 : 1 0 −1, 25 0, 25 3, 75
Um corte pode ser gerado a partir de uma solução fracionária notableau (exemplo acima).
Seja a segunda restrição (r2):
x1 − 1, 25s1 + 0, 25s2 = 3, 75
Podemos utilizá-la para gerar cortes de Gomory!
23 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Cortes de Gomory
x1 x2 x3 x4 rhs
z : 0 0 1, 25 0, 75 5, 25
r1 : 0 1 2, 25 −0, 25 2, 25
r2 : 1 0 −1, 25 0, 25 3, 75
Como as variáveis são inteiras (lembre-se do arredondamento):
x1 − b1, 25cs1 + b0, 25cs2 ≤ b3, 75c ∴ x1 − 2s1 − 3 ≤ 0
Se separamos a parte inteira da fracionária, teríamos:
x1 + (−2 + 0, 75)s1 + (0 + 0, 25)s2 = (3 + 0, 75)
x1− 2s1 − 3 = 0, 75− 0, 75s1 − 0, 25s2
0, 75− 0, 75s1 − 0, 25s2 ≤ 0
24 / 24 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Recommended