Aula 14: ModelagemOtimização Linear e Inteira
Túlio A. M. Toffolohttp://www.toffolo.com.br
BCC464/PCC174 –2018/2Departamento de Computação –UFOP
Previously...
Modelagem em PI / Problemas Combinatórios
Programação Linear vs Inteira
Branch-and-bound
2 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
Aula de Hoje
1 Problema do Caixeiro Viajante
2 Formulação 1
3 Formulação 2
3 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
Aula de Hoje
1 Problema do Caixeiro Viajante
2 Formulação 1
3 Formulação 2
3 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
O 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 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
Caixeiro Viajante - Exemplo
f
c g
e
a j m
n
p
qk
o
l
h
id
b
r
Solução viável: um circuito Hamiltoniano no Grafo.
5 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
Caixeiro Viajante - Exemplo
f
c g
e
a j m
n
p
qk
o
l
h
id
b
r
Solução viável: um circuito Hamiltoniano no Grafo.
5 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
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
6 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
Sub-rotas
f
c g
e
a j m
n
p
qk
o
l
h
id
b
r
7 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
Removendo 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
8 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
Removendo Sub-Rotas (alternativa)
ou
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
PS: há livros dedicados inteiramente ao TSP; exemplos:
Applegate, D., R. Bixby, V. Chvátal, and W. Cook (2006). TheTraveling Salesman Problem. A computational study, PrincetonUniversity
Lawer, E., J.K. Lenstra, A. Rinnooy Kan, and D. Shmoys (editors)(1985). The Traveling Salesman Problem, Wiley, New York.
9 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
Aula de Hoje
1 Problema do Caixeiro Viajante
2 Formulação 1
3 Formulação 2
10 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
Variáveis
xi,j =
{1 se o arco (i, j) ∈ A fará parte da rota0 caso contrário
ui = ordem (posição) da cidade i (ui ≥ 0)
Formulação
min∑
(i,j)∈A
ci,jxi,j
s.a.∑
j:(i,j)∈A
xi,j =∑
j:(j,i)∈A
xj,i = 1 ∀i ∈ V
u1 = 1
ui − uj + nxi,j ≤ n− 1 ∀(i, j) ∈ A : j 6= 1
xi,j ∈ {0, 1}, ui ≥ 0 ∀(i, j) ∈ A
11 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
Aula de Hoje
1 Problema do Caixeiro Viajante
2 Formulação 1
3 Formulação 2
12 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
Variáveis
xi,j =
{1 se o arco (i, j) ∈ A fará parte da rota0 caso contrário
Formulação
min∑
(i,j)∈A
ci,jxi,j
s.a.∑
j:(i,j)∈A
xi,j =∑
j:(j,i)∈A
xj,i = 1 ∀i ∈ V
∑(i,j)∈A:i∈S,j∈S
xi,j ≤ |S| − 1 ∀S ⊂ V, 2 ≤ |S| ≤ n− 1
xi,j ∈ {0, 1} ∀(i, j) ∈ A
13 / 13 Túlio Toffolo – Otimização Linear e Inteira – Aula 14: Modelagem
/ 12
Perguntas?