13_branch_and_bound

Prévia do material em texto

Aula 13: Branch-and-bound
Otimização Linear e Inteira
Túlio A. M. Toffolo
http://www.toffolo.com.br
BCC464/PCC174 –2018/2
Departamento de Computação –UFOP
Previously...
Modelagem em PI / Problemas Combinatórios
Caixeiro Viajante
Cobertura de Conjuntos
Programação Linear vs Inteira
Exercícios
2 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Aula de Hoje
1 Breve revisão
2 Branch-and-bound
3 Exercícios (aula passada)
4 Exercício
3 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Aula de Hoje
1 Breve revisão
2 Branch-and-bound
3 Exercícios (aula passada)
4 Exercício
3 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Conceito
Relaxação
Uma formulaçãoR = {min fR(x) : x ∈ XR} é considerada uma
relaxação de uma formulaçãoM = {min f(x) : x ∈ X} se:
1 todas as soluções deM são também soluções deR, ou seja,
X ⊆ XR,
2 e toda solução x ∈ X tem custo emR menor ou igual ao custo em
M, ou seja, fR(x) ≤ f(x) para todo x ∈ X
Exemplo: relaxação linear
4 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Exemplo
Maximize z = 6x1 + 5x2
Sujeito a 15x1 + 7x2 ≤ 49
2x1 + 4x2 ≤ 17
x1, x2 ∈ Z+
5 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Exemplo
Maximize:
6x1 + 5x2
Sujeito a:
15x1 + 7x2 ≤ 49
2x1 + 4x2 ≤ 17
x1, x2 ∈ Z+
Não é ponto inteiro!
 
1
2
3
4
1 2 3 4
6 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Exemplo
Maximize:
6x1 + 5x2
Sujeito a:
15x1 + 7x2 ≤ 49
2x1 + 4x2 ≤ 17
x1, x2 ∈ Z+
z = 27, 11 em
x1 = 1, 7 e x2 = 3, 4
Não é ponto inteiro!
Ótimo inteiro: z = 22
em
x1 = 2 e x2 = 2
 
1
2
3
4
1 2 3 4
6 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
A Formulação Ideal
Maximize:
6x1 + 5x2
Sujeito a:
2x1 + 2x2 ≤ 8
6x1 + 3x2 ≤ 18
x1, x2 ∈ R+
Formulação ideal
envoltória convexa
dos pontos inteiros
válidos
 
1
2
3
4
1 2 3 4
7 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
A Formulação Ideal
Teorema
Quando o poliedro definido pelas restrições define a envoltória convexa
das soluções inteiras válidas, o Programa Inteiro pode ser resolvido
como um Programa Linear, ou seja, as restrições de integralidade
podem ser ignoradas e a solução ótima fornecida para esse problema
relaxado ainda assim será uma solução inteira.
No entanto... Obter tal poliedro não é trivial. :(
8 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Como resolver problemas de Programação Inteira (PI)?
Solvers de PI incluem:
Branch-and-bound
Algoritmos de plano de corte
Heurísticas
etc.
9 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Aula de Hoje
1 Breve revisão
2 Branch-and-bound
3 Exercícios (aula passada)
4 Exercício
10 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Branch-and-bound
Idéia Básica
O algoritmo cria uma árvore de enumeração para explorar as soluções
possíveis;
No pior caso, todas as soluções serão exploradas.
Na prática, frequentemente vários ramos da árvore são podados com
o uso de limites (bounds).
11 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Branch-and-bound
Branch (ramificar)
Consiste em dividir um problema em problemas menores.
Divide-se um problema P em m subproblemas, tais que:
P1, P2, . . . , Pm tal que
P1 ∪ P2, . . . ,∪Pm = P
Geralmente divide-se o problema em 2 subproblemas em cada passo.
12 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Branch-and-bound
Ex.: Problema com 3 variáveis binárias: x1, x2, x3.
P
P1 P2
P11 P12 P21 P12
P11 P12 P11 P12 P11 P12 P11 P12
x1=0
x2=0x2=1x2=0x2=1
x1=1
x3=0x3=1x3=0x3=1x3=0x3=1x3=0x3=1
13 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Branch-and-bound
Bound (limites)
O branch resulta em um algoritmo exato que encontra a solução ótima
em um número finito de passos, mas...
É extremamente ineficiente!
Para n variáveis binárias teremos 2n nós a serem explorados.
A chave para melhorar a eficiência do algoritmo é a poda de
sub-árvores através do uso de limites.
14 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Bound - Limites
Para um problema de maximização:
z = max f(x)
Podemos encontrar limites que
permitem avalizar a qualidade de
uma solução com custo f(x).
z
z
z
Limite Superior
Solução Ótima
Limite Inferior
15 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Exemplo - Problema da Mochila
Problema clássico conhecido como The
Knapsack Problem
Dado um conjunto de itens e uma
pequena mochila, temos que decidir
quais itens carregar.
Cada item tem um peso e um valor.
Queremos maximizar o valor.
16 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Exemplo - Problema da Mochila
Cada item i ∈ I tem peso wi e valor vi.
A capacidade da mochila é dada por C.
xi =
{
1 se item i está na mochila
0 caso contrário
Maximizar
∑
i∈I
vixi
Sujeito a
∑
i∈I
wixi ≤ C
xi ∈ {0, 1}
17 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Exemplo - Problema da Mochila
Como calcular rapidamente um limite superior para o valor?
Relaxação linear: o Problema Fracionário da Mochila (PFM)
Trocamos xi ∈ {0, 1} por 0 ≤ xi ≤ 1, ou seja, agora podemos
colocar “pedaços” de itens;
A solução ótima para o PFM é fácil de calcular: resolvemos o modelo
relaxado via Simplex ou:
1 Colocamos os itens com maior densidade di =
vi
wi
2 Até um item não caber na mochila: então colocamos a maior fração
possível dele
18 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Exemplo - Problema da Mochila
Exemplo: problema com 4 itens e C = 6:
item valor peso ‘densidade’
1 7 4 1,75
2 4 3 1,33
3 9 5 1,80
4 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 ou
igual a 10,75, ou seja, obtemos um limite superior.
19 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Exemplo - Problema da Mochila
Como calcular rapidamente um limite inferior para o valor?
(ou obter uma solução viável?)
Heurística gulosa
Tentamos colocar os itens com grande valor e pouco peso.
1 Ordenamos os itens por densidade di =
vi
wi
2 Enquanto houver capacidade suficiente, adicionamos na mochila o
item i com maior valor cujo peso seja inferior à capacidade restante da
mochila.
20 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Exemplo - Problema da Mochila
Exemplo: problema com 4 itens e C = 6:
item valor peso ‘densidade’
1 7 4 1,75
2 4 3 1,33
3 9 5 1,80
4 3 2 1,50
Solução da heurística gulosa
Solução heurística: itens: {3}, valor: 9
A solução ótima com certeza é maior ou igual a 9, ou seja, temos um
limite inferior para o custo da solução ótima.
21 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Exemplo - Problema da Mochila
Exemplo anterior com 4 itens e C = 6:
Limites Encontrados
Limite Superior (Relaxação Linear) 10,75
↓
? ótimo ? ?
↑
Limite Inferior (Heurística Gulosa) 9
22 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Definições
Soluções Parciais
Tanto a heurística quanto a relaxação linear podem ser executadas em
nós internosda árvore, considerando algumas fixações de variáveis.
No exemplo do Problema da Mochila: atualiza-se a capacidade restante e
items disponíveis.
Esse procedimento permite calcular:
Limite Inferior: quando o nó produz uma solução viável.
Limite Superior: quando é possível gerar uma solução viável
considerando as fixações feitas nó.
23 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Definições
Solução Incumbente
É a melhor solução encontrada até o momento durante a busca. Essa
solução pode aparecer durante a execução de uma heurística ou durante
o percurso na árvore (ao se chegar em nós folha).
No caso de Maximização, temos um Limite Inferior.
No caso de Minimização, temos um Limite Superior.
24 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Poda
Quando podemos podar uma subárvore?
1. Quando os limites (bounds) permitem
Quando a relaxação indica que não há possibilidade de se melhorar a
solução incumbente.
No Problema da Mochila, ocorre quando o limite superior (relaxação) é
menor do que o melhor limite inferior conhecido.
2. Quando o nó é infactível/inviável
Quando as fixações já feitas induzem a soluções inviáveis;
No Problema da Mochila, quando as fixações excedem a capacidade
da mochila, por exemplo.
25 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Branch-and-bound: Problema da Mochila
item vi wi di
1 7 4 1,75
2 4 3 1,33
3 9 5 1,80
4 3 2 1,50
5 :X
, -1/4,113=1
10,75/9
5 :×z=1
X. =
 1 Xy =O
5 : × , -1,113=45 5×3=1
, 114=1/2
six'=' 1×4=1 10,6/10 10,5 / 9 si×3=
'
3=1
×3=0 ×4=1 ×y=O
X 5 :X
} -45,114=1 § : xa.it/3,Xz=1
inviavel yosinfueeiarjo 10,2/7si×a=110,33/9 si×3= '
5:X , --X4=1 13=1 113=0
×2=1*
 poda ×2=O
por limit
inviavel
7 sinfueeirjo 9,4/4 g sdueaointeira
5 :X4=1 5 :Xa=1
, .×s=
5 :×z=1
S :Xa=1
26 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Aula de Hoje
1 Breve revisão
2 Branch-and-bound
3 Exercícios (aula passada)
4 Exercício
27 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Ex. 1: Sudoku
5 3 . . 7 . . . .
6 . . 1 9 5 . . .
. 9 8 . . . . 6 .
8 . . . 6 . . . 3
4 . . 8 . 3 . . 1
7 . . . 2 . . . 6
. 6 . . . . 2 8 .
. . . 4 1 9 . . 5
. . . . 8 . . 7 9
Apresente um modelo de Programação Inteira que resolva o Sudoku.
28 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Entrada
d(i,j) : i, j ∈ {1 . . . 9} ∪ {0}
d(i,j) é zero caso o valor da posição i, j não seja informada
ou o número informado
Variáveis
xi,j,k = 1 se o valor k é inserido na posição i, j e 0 c.c.
Restrições (parte I)
xi,j,d(i,j) = 1 ∀i, j ∈ {1 . . . 9} : d(i,j) 6= 0
9∑
k=1
xi,j,k = 1 ∀i, j ∈ {1 . . . 9}
29 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Entrada
d(i,j) : i, j ∈ {1 . . . 9} ∪ {0}
d(i,j) é zero caso o valor da posição i, j não seja informada
ou o número informado
Restrições (parte I)
9∑
j=1
xi,j,k ≤ 1 ∀i ∈ {1 . . . 9}, k ∈ {1 . . . 9}
9∑
i=1
xi,j,k ≤ 1 ∀j ∈ {1 . . . 9}, k ∈ {1 . . . 9}
n+2∑
i=n
m+2∑
j=m
xi,j,k ≤ 1 ∀n,m ∈ {1, 4, 7}, k ∈ {1 . . . 9}
30 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
a b c d e f g h
1
2
3
4
5
6
7
8
31 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Variáveis
xi,j = 1 se uma rainha é alocada na posição i, j e 0 c.c.
Restrições (parte I)
n∑
i=1
n∑
j=1
xi,j = n
n∑
i=1
xi,j ≤ 1 ∀j ∈ {1 . . . n}
n∑
j=1
xi,j ≤ 1 ∀i ∈ {1 . . . n}
32 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Variáveis
xi,j = 1 se uma rainha é alocada na posição i, j e 0 c.c.
Restrições (parte II)
n−i∑
k=0
xi+k,1+k ≤ 1 ∀i ∈ {1 . . . n}
n−j∑
k=0
x1+k,j+k ≤ 1 ∀j ∈ {1 . . . n}
j−1∑
k=0
x1+k,j−k ≤ 1 ∀j ∈ {1 . . . n}
n−i∑
k=0
xi+k,n−k ≤ 1 ∀i ∈ {1 . . . n}
33 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Aula de Hoje
1 Breve revisão
2 Branch-and-bound
3 Exercícios (aula passada)
4 Exercício
34 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
Problema da Mochila
Exercício para aula prática
Implementar um modelo (no gurobi) que resolva o problema da mochila.
Dados serão disponibilizados num arquivo csv
(exceto capacidade, que é sempre igual a 100)
Exemplo:
1 item;peso;valor
2 1;10;10
3 2;10;10
4 ...
Obs: utilize a linguagem de programação de sua preferência.
35 / 35 Túlio Toffolo – Otimização Linear e Inteira – Aula 13: Branch-and-bound
 / 12
Perguntas?
	Breve revisão
	Branch-and-bound
	Exercícios (aula passada)
	Exercício