Aula 17: Planos de CorteOtimização Linear e Inteira
Túlio A. M. Toffolohttp://www.toffolo.com.br
BCC464/PCC174 – 2019/2Departamento de Computação – UFOP
Previously...
Branch-and-bound em programação inteira
Desigualdades válidas
Cortes combinatórios
(continuação hoje...)
2 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Aula de Hoje
1 Cortes Combinatórios
2 Caixeiro Viajante - Algoritmo de plano de cortes
3 Cortes Baseados em ArredondamentoExemplo de arredondamentoCortes de Chvátal-GomoryCortes de Gomory
4 Exercícios
3 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Cortes da Mochila
Considere que variáveis binárias xj aparecem numa restrição do tipo:∑j∈N
ajxj ≤ b (aj ≥ 0 para todo j ∈ N)
Um Conjunto C ⊆ N é uma Cobertura (Cover) se:∑j∈C
ajxj > b
O que define o seguinte Corte de Cover :∑j∈C
xj ≤ |C| − 1
4 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Cortes de Cover
Exemplo
Considere a seguinte restrição sobre as variáveis binárias xj :
11x1 + 6x2 + 6x3 + 5x4 + 5x5 + 4x6 + x7 ≤ 19
Alguns cortes de cover:
x1 + x2 + x3 ≤ 2
x1 + x2 + x6 ≤ 2
x1 + x5 + x6 ≤ 2
x3 + x4 + x5 + x6 ≤ 3
Os cortes acima são cortes de cover minimais, no sentido que qualquer variávelretirada da restrição descaracteriza a cobertura.
5 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Exemplo - Problema da Mochila
Exemplo: problema com 4 itens e C = 6:
item valor peso ‘densidade’1 7 4 1,752 4 3 1,333 9 5 1,804 3 2 1,50
Solução ótima da relaxação linear
seleciona item 3
seleciona 14 do item 1
solução com valor 10,75
A solução ótima do problema da mochila 0-1 é portanto menor ouigual a 10,75, ou seja, obtemos um limite superior.
6 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Cortes de Cover : separação
Considere a solução fracionária x∗.
Desigualdades violadas de Cover podem ser geradas resolvendo-se oproblema DP:
DP =
σ(x∗) = min
∑j∈N
(1− x∗j )zj
s.a.∑j∈N
ajzj > b
zj ∈ {0, 1} ∀j ∈ N
Uma desigualdade válida violada de cover é descoberta quando tem-sez∗ com σ(x∗) < 1.
7 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Empacotamento de Nós
Cliques
x1 + x2 + x3 + x4 + x5 ≤ 1
x1
x2 x3
x4 x5
8 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Empacotamento de Nós
Ciclo Ímpar
x1 + x2 + x3 + x4 + x5 ≤ 2
x1
x2x5
x4 x3
9 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Empacotamento de Nós
Roda
2x6+x1+x2+x3+x4+x5 ≤ 2
x1
x2x5
x4 x3
x6
10 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Aula de Hoje
1 Cortes Combinatórios
2 Caixeiro Viajante - Algoritmo de plano de cortes
3 Cortes Baseados em ArredondamentoExemplo de arredondamentoCortes de Chvátal-GomoryCortes de Gomory
4 Exercícios
11 / 33 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.
12 / 33 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
13 / 33 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
14 / 33 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
15 / 33 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.
16 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Aula de Hoje
1 Cortes Combinatórios
2 Caixeiro Viajante - Algoritmo de plano de cortes
3 Cortes Baseados em ArredondamentoExemplo de arredondamentoCortes de Chvátal-GomoryCortes de Gomory
4 Exercícios
17 / 33 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)
18 / 33 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
19 / 33 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.
20 / 33 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
21 / 33 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
21 / 33 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)
22 / 33 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)
23 / 33 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
24 / 33 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
25 / 33 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
25 / 33 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
25 / 33 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
26 / 33 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
27 / 33 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)
28 / 33 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
29 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Cortes de Gomory
x1 x2 s1 s2 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!
30 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Cortes de Gomory
x1 x2 s1 s2 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
31 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Aula de Hoje
1 Cortes Combinatórios
2 Caixeiro Viajante - Algoritmo de plano de cortes
3 Cortes Baseados em ArredondamentoExemplo de arredondamentoCortes de Chvátal-GomoryCortes de Gomory
4 Exercícios
32 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
Exemplo - Problema da Mochila
Exemplo: problema com 4 itens e C = 6:
item valor peso ‘densidade’1 7 4 1,752 4 3 1,333 9 5 1,804 3 2 1,50
ExercícioEncontre uma desigualdade de cobertura (cover) violada para a soluçãoótima da relaxação do problema apresentado (solução a seguir).{x1 =
1
4, x2 = 0, x3 = 1, x4 = 0
}, com custo z = 10, 75
33 / 33 Túlio Toffolo – Otimização Linear e Inteira – Aula 17: Planos de Corte
/ 12
Perguntas?