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?