Aula 13: Branch-and-bound - Otimização Linear e Inteira · 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

Aula 13: Branch-and-boundOtimização Linear e Inteira

Túlio A. M. Toffolohttp://www.toffolo.com.br

BCC464/PCC174 –2018/2Departamento de Computação –UFOP

http://www.toffolo.com.br

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


Aula de Hoje

1 Breve revisão

2 Branch-and-bound


4 Exercício


Conceito

Relaxação

Uma formulaçãoR = {min fR(x) : x ∈ XR} é considerada umarelaxaçã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 emM, ou seja, fR(x) ≤ f(x) para todo x ∈ X

Exemplo: relaxação linear


Exemplo

Maximize z = 6x1 + 5x2

Sujeito a 15x1 + 7x2 ≤ 49

2x1 + 4x2 ≤ 17

x1, x2 ∈ Z+


Exemplo

Maximize:6x1 + 5x2

Sujeito a:15x1 + 7x2 ≤ 492x1 + 4x2 ≤ 17x1, x2 ∈ Z+

Não é ponto inteiro!

1

2

3

4

1 2 3 4


Exemplo

Maximize:6x1 + 5x2

Sujeito a:15x1 + 7x2 ≤ 492x1 + 4x2 ≤ 17x1, x2 ∈ Z+

z = 27, 11 emx1 = 1, 7 e x2 = 3, 4

Não é ponto inteiro!

Ótimo inteiro: z = 22emx1 = 2 e x2 = 2

1

2

3

4

1 2 3 4


A Formulação Ideal

Maximize:6x1 + 5x2

Sujeito a:2x1 + 2x2 ≤ 86x1 + 3x2 ≤ 18x1, x2 ∈ R+

Formulação ideal

envoltória convexados pontos inteirosválidos

1

2

3

4

1 2 3 4


A Formulação Ideal

TeoremaQuando o poliedro definido pelas restrições define a envoltória convexadas soluções inteiras válidas, o Programa Inteiro pode ser resolvidocomo um Programa Linear, ou seja, as restrições de integralidadepodem ser ignoradas e a solução ótima fornecida para esse problemarelaxado ainda assim será uma solução inteira.

No entanto... Obter tal poliedro não é trivial. :(


Como resolver problemas de Programação Inteira (PI)?

Solvers de PI incluem:

Branch-and-bound

Algoritmos de plano de corte

Heurísticas

etc.


Aula de Hoje

1 Breve revisão

2 Branch-and-bound


4 Exercício


Branch-and-bound

Idéia Básica

O algoritmo cria uma árvore de enumeração para explorar as soluçõespossíveis;

No pior caso, todas as soluções serão exploradas.

Na prática, frequentemente vários ramos da árvore são podados como uso de limites (bounds).


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.


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


Branch-and-bound

Bound (limites)

O branch resulta em um algoritmo exato que encontra a solução ótimaem 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 desub-árvores através do uso de limites.


Bound - Limites

Para um problema de maximização:

z = max f(x)

Podemos encontrar limites quepermitem avalizar a qualidade deuma solução com custo f(x).

z

z

z

Limite Superior

Solução Ótima

Limite Inferior


Exemplo - Problema da Mochila

Problema clássico conhecido como TheKnapsack Problem

Dado um conjunto de itens e umapequena mochila, temos que decidirquais itens carregar.

Cada item tem um peso e um valor.

Queremos maximizar o valor.



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}



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 podemoscolocar “pedaços” de itens;

A solução ótima para o PFM é fácil de calcular: resolvemos o modelorelaxado via Simplex ou:

1 Colocamos os itens com maior densidade di =viwi

2 Até um item não caber na mochila: então colocamos a maior fraçãopossível dele



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.



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 =viwi

2 Enquanto houver capacidade suficiente, adicionamos na mochila oitem i com maior valor cujo peso seja inferior à capacidade restante damochila.



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 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 umlimite inferior para o custo da solução ótima.



Exemplo anterior com 4 itens e C = 6:

Limites Encontrados

Limite Superior (Relaxação Linear) 10,75↓

? ótimo ? ?↑

Limite Inferior (Heurística Gulosa) 9


Definições

Soluções Parciais

Tanto a heurística quanto a relaxação linear podem ser executadas emnós internos da árvore, considerando algumas fixações de variáveis.

No exemplo do Problema da Mochila: atualiza-se a capacidade restante eitems 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ávelconsiderando as fixações feitas nó.


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 duranteo 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.


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 asoluçã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ávelQuando as fixações já feitas induzem a soluções inviáveis;

No Problema da Mochila, quando as fixações excedem a capacidadeda mochila, por exemplo.


Branch-and-bound: Problema da Mochila

item vi wi di1 7 4 1,752 4 3 1,333 9 5 1,804 3 2 1,50

5 :X, -1/4,113=1

10,75/95 :×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 / 9si×3= '

3=1×3=0 ×4=1

×y=O

X 5 :X} -45,114=1 §

: xa.it/3,Xz=1inviavel yosinfueeiarjo 10,2/7si×a=1

10,33/9 si×3= '

5:X, --X4=1 13=1 113=0

×2=1* poda ×2=O

por limit

inviavel7 sinfueeirjo 9,4/4 g sdueao

inteira

5 :X4=1 5 :Xa=1, .×s= 5 :×z=1

S :Xa=1


Aula de Hoje

1 Breve revisão

2 Branch-and-bound


4 Exercício


Ex. 1: Sudoku

5 3 . . 7 . . . .6 . . 1 9 5 . . .. 9 8 . . . . 6 .8 . . . 6 . . . 34 . . 8 . 3 . . 17 . . . 2 . . . 6. 6 . . . . 2 8 .. . . 4 1 9 . . 5. . . . 8 . . 7 9

Apresente um modelo de Programação Inteira que resolva o Sudoku.


Entrada

d(i,j) : i, j ∈ {1 . . . 9} ∪ {0}d(i,j) é zero caso o valor da posição i, j não seja informadaou 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}


Entrada

d(i,j) : i, j ∈ {1 . . . 9} ∪ {0}d(i,j) é zero caso o valor da posição i, j não seja informadaou o número informado


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}


a b c d e f g h

1

2

3

4

5

6

7

8


Variáveisxi,j = 1 se uma rainha é alocada na posição i, j e 0 c.c.


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}


Variáveisxi,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}


Aula de Hoje

1 Breve revisão

2 Branch-and-bound


4 Exercício


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;valor2 1;10;103 2;10;104 ...

Obs: utilize a linguagem de programação de sua preferência.


/ 12

Perguntas?

Documents

Aula 13: Branch-and-bound - Otimização Linear e Inteira · 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