88
Introdu¸c˜ ao ` a Otimiza¸ aoCombinat´oria etodos Exatos para PI - Parte 2: Planos de Corte e Branch-and-Cut Professora: Rosiane de Freitas ([email protected]) Bruno Raphael Cardoso Dias Prof. Est´ agio em Docˆ encia ([email protected]) Universidade Federal do Amazonas - UFAM Instituto de Computa¸c˜ ao - IComp Manaus-AM, Brasil Maio de 2015 Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 1 / 31

Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Embed Size (px)

Citation preview

Page 1: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Introducao a Otimizacao CombinatoriaMetodos Exatos para PI - Parte 2: Planos de Corte e

Branch-and-Cut

Professora:

Rosiane de Freitas([email protected])

Bruno Raphael Cardoso Dias

Prof. Estagio em Docencia

([email protected])

Universidade Federal do Amazonas - UFAMInstituto de Computacao - IComp

Manaus-AM, Brasil

Maio de 2015

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 1 / 31

Page 2: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte

Ideia para pensar

Como visto no metodo branch-and-bound, a solucao da relaxacaolinear de um problema de minimizacao em PI e um limite inferior parao PPI original (e um limite superior se o problema for demaximizacao)

Logo, existem pontos contınuos que estao fora da maior regiao quecontem os pontos inteiros mais extremos e que satisfazem asrestricoes.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 2 / 31

Page 3: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte

Ideia para pensar

Como visto no metodo branch-and-bound, a solucao da relaxacaolinear de um problema de minimizacao em PI e um limite inferior parao PPI original (e um limite superior se o problema for demaximizacao)

Logo, existem pontos contınuos que estao fora da maior regiao quecontem os pontos inteiros mais extremos e que satisfazem asrestricoes.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 2 / 31

Page 4: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte

Planos de Corte

Temos a seguinte regiao viavel paraa relaxacao contınua de umproblema de PI...

Mas a menor regiao que contemtodos os pontos inteiros e menor(ao lado - este e o chamado fechoconvexo dos pontos inteiros)...

Entao, podemos remover pontosadicionando algum dado no nossoproblema que seja satisfeito portodas solucoes inteiras mas naotodas as contınuas!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 3 / 31

Page 5: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte

Planos de Corte

Temos a seguinte regiao viavel paraa relaxacao contınua de umproblema de PI...

Mas a menor regiao que contemtodos os pontos inteiros e menor(ao lado - este e o chamado fechoconvexo dos pontos inteiros)...

Entao, podemos remover pontosadicionando algum dado no nossoproblema que seja satisfeito portodas solucoes inteiras mas naotodas as contınuas!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 4 / 31

Page 6: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte

Planos de Corte

Temos a seguinte regiao viavel paraa relaxacao contınua de umproblema de PI...

Mas a menor regiao que contemtodos os pontos inteiros e menor(ao lado - este e o chamado fechoconvexo dos pontos inteiros)...

Entao, podemos remover pontosadicionando algum dado no nossoproblema que seja satisfeito portodas solucoes inteiras mas naotodas as contınuas!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 5 / 31

Page 7: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte

Planos de Corte

Um plano de corte define uma restricao a mais para o problema queelimina pontos extremos contınuos, sem, no entanto, removernenhum ponto inteiro factıvel.

O que queremos aqui e, eventualmente, colocar a solucao otima doproblema de PI como um vertice do politopo, de forma que o Simplexencontre o mesmo e retorne a solucao!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 6 / 31

Page 8: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte

Planos de Corte

Um plano de corte define uma restricao a mais para o problema queelimina pontos extremos contınuos, sem, no entanto, removernenhum ponto inteiro factıvel.

O que queremos aqui e, eventualmente, colocar a solucao otima doproblema de PI como um vertice do politopo, de forma que o Simplexencontre o mesmo e retorne a solucao!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 6 / 31

Page 9: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

A partir de uma solucao contınua da relaxacao em PL do problema dePI, resolvida pelo Simplex, podemos usar os dados que temos paracriar uma nova restricao que corta pontos contınuos do politopo.

Para comecar, lembremos que todo valor real x possui uma parteinteira e uma parte fracionaria, onde a parte inteira e representadapor bxc (como ja mostrado) e a parte fracionaria e x − bxcDenotaremos a parte inteira da variavel xi do problema como ni e aparte fracionaria como fi .

Da mesma forma, denotaremos a parte inteira do coeficiente aij damatriz de restricoes como nij e a parte fracionaria como fij ..

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 7 / 31

Page 10: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

A partir de uma solucao contınua da relaxacao em PL do problema dePI, resolvida pelo Simplex, podemos usar os dados que temos paracriar uma nova restricao que corta pontos contınuos do politopo.

Para comecar, lembremos que todo valor real x possui uma parteinteira e uma parte fracionaria, onde a parte inteira e representadapor bxc (como ja mostrado) e a parte fracionaria e x − bxc

Denotaremos a parte inteira da variavel xi do problema como ni e aparte fracionaria como fi .

Da mesma forma, denotaremos a parte inteira do coeficiente aij damatriz de restricoes como nij e a parte fracionaria como fij ..

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 7 / 31

Page 11: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

A partir de uma solucao contınua da relaxacao em PL do problema dePI, resolvida pelo Simplex, podemos usar os dados que temos paracriar uma nova restricao que corta pontos contınuos do politopo.

Para comecar, lembremos que todo valor real x possui uma parteinteira e uma parte fracionaria, onde a parte inteira e representadapor bxc (como ja mostrado) e a parte fracionaria e x − bxcDenotaremos a parte inteira da variavel xi do problema como ni e aparte fracionaria como fi .

Da mesma forma, denotaremos a parte inteira do coeficiente aij damatriz de restricoes como nij e a parte fracionaria como fij ..

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 7 / 31

Page 12: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

A partir de uma solucao contınua da relaxacao em PL do problema dePI, resolvida pelo Simplex, podemos usar os dados que temos paracriar uma nova restricao que corta pontos contınuos do politopo.

Para comecar, lembremos que todo valor real x possui uma parteinteira e uma parte fracionaria, onde a parte inteira e representadapor bxc (como ja mostrado) e a parte fracionaria e x − bxcDenotaremos a parte inteira da variavel xi do problema como ni e aparte fracionaria como fi .

Da mesma forma, denotaremos a parte inteira do coeficiente aij damatriz de restricoes como nij e a parte fracionaria como fij ..

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 7 / 31

Page 13: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

Lembrando do Quadro Simplex (n variaveis e m restricoes):

x1 x2 ... xn b

xB1 y11 y12 ... y1n b1

xB2 y21 y22 ... y2n b2

... ... ... ... ... ...xBm ym1 ym2 ... ymn bm−z x1∗ x2∗ ... xn∗ b0

Onde a linha −z indica os valores das variaveis e funcao objetivo noponto otimo e as outras linhas correspondem as m restricoes (tendom elementos na base).

Temos tambem que xB sao as variaveis basicas (a base e B) e xN saoas variaveis nao basicas (N = B).

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 8 / 31

Page 14: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

A i-esima linha do quadro e, entao:∑k∈B

aikxBk +

∑j∈N

aijxNj = bi

Apenas a variavel basica xBi tem coeficiente 1 na linha (as outras temcoeficiente 0), portanto, tem-se:

xBi +∑j∈N

aijxNj = bi

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 9 / 31

Page 15: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

A i-esima linha do quadro e, entao:∑k∈B

aikxBk +

∑j∈N

aijxNj = bi

Apenas a variavel basica xBi tem coeficiente 1 na linha (as outras temcoeficiente 0), portanto, tem-se:

xBi +∑j∈N

aijxNj = bi

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 9 / 31

Page 16: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

Equivalentemente:

xBi = bi −∑j∈N

aijxNj

Lembrando a decomposicao dos numeros em partes fracional edecimal:

bi = ni + fiaij = nij + fij

Substituindo os valores da decomposicao na equacao da linha eagrupando as partes, teremos:

xBi =

ni −∑j∈N

nijxNj

+

fi −∑j∈N

fijxNj

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 10 / 31

Page 17: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

Equivalentemente:

xBi = bi −∑j∈N

aijxNj

Lembrando a decomposicao dos numeros em partes fracional edecimal:

bi = ni + fiaij = nij + fij

Substituindo os valores da decomposicao na equacao da linha eagrupando as partes, teremos:

xBi =

ni −∑j∈N

nijxNj

+

fi −∑j∈N

fijxNj

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 10 / 31

Page 18: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

Equivalentemente:

xBi = bi −∑j∈N

aijxNj

Lembrando a decomposicao dos numeros em partes fracional edecimal:

bi = ni + fiaij = nij + fij

Substituindo os valores da decomposicao na equacao da linha eagrupando as partes, teremos:

xBi =

ni −∑j∈N

nijxNj

+

fi −∑j∈N

fijxNj

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 10 / 31

Page 19: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

A primeira parcela da soma acima e inteira, ja que todos os valores nsao inteiros. A segunda parcela e um resultado menor que 1, pois:

a) fi < 1b) Todos fij ≥ 0c) Todos xNj ≥ 0

Como a segunda parcela deve ser inferior a 1 e tambem ser inteirapara que satisfaca a restricao de integralidade que desejamos, temos:

fi −∑j∈N

fijxNj ≤ 0

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 11 / 31

Page 20: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

A primeira parcela da soma acima e inteira, ja que todos os valores nsao inteiros. A segunda parcela e um resultado menor que 1, pois:

a) fi < 1b) Todos fij ≥ 0c) Todos xNj ≥ 0

Como a segunda parcela deve ser inferior a 1 e tambem ser inteirapara que satisfaca a restricao de integralidade que desejamos, temos:

fi −∑j∈N

fijxNj ≤ 0

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 11 / 31

Page 21: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

A primeira parcela da soma acima e inteira, ja que todos os valores nsao inteiros. A segunda parcela e um resultado menor que 1, pois:

a) fi < 1b) Todos fij ≥ 0c) Todos xNj ≥ 0

Como a segunda parcela deve ser inferior a 1 e tambem ser inteirapara que satisfaca a restricao de integralidade que desejamos, temos:

fi −∑j∈N

fijxNj ≤ 0

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 11 / 31

Page 22: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

Ou seja:

−∑j∈N

fijxNj ≤ −fi →

∑j∈N

fijxNj ≥ fi

Esta inequacao e o Corte de Gomory.

A aplicacao repetida destes cortes no problema relaxado garante quechegaremos ao ponto otimo inteiro!

Note que a adicao da inequacao implica, naturalmente, em umaumento do tamanho da base do Simplex e em uma variavel de folgaa mais!

Observe tambem que este e um metodo de geracao de linhas!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 12 / 31

Page 23: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

Ou seja:

−∑j∈N

fijxNj ≤ −fi →

∑j∈N

fijxNj ≥ fi

Esta inequacao e o Corte de Gomory.

A aplicacao repetida destes cortes no problema relaxado garante quechegaremos ao ponto otimo inteiro!

Note que a adicao da inequacao implica, naturalmente, em umaumento do tamanho da base do Simplex e em uma variavel de folgaa mais!

Observe tambem que este e um metodo de geracao de linhas!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 12 / 31

Page 24: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

Ou seja:

−∑j∈N

fijxNj ≤ −fi →

∑j∈N

fijxNj ≥ fi

Esta inequacao e o Corte de Gomory.

A aplicacao repetida destes cortes no problema relaxado garante quechegaremos ao ponto otimo inteiro!

Note que a adicao da inequacao implica, naturalmente, em umaumento do tamanho da base do Simplex e em uma variavel de folgaa mais!

Observe tambem que este e um metodo de geracao de linhas!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 12 / 31

Page 25: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

Ou seja:

−∑j∈N

fijxNj ≤ −fi →

∑j∈N

fijxNj ≥ fi

Esta inequacao e o Corte de Gomory.

A aplicacao repetida destes cortes no problema relaxado garante quechegaremos ao ponto otimo inteiro!

Note que a adicao da inequacao implica, naturalmente, em umaumento do tamanho da base do Simplex e em uma variavel de folgaa mais!

Observe tambem que este e um metodo de geracao de linhas!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 12 / 31

Page 26: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

Ou seja:

−∑j∈N

fijxNj ≤ −fi →

∑j∈N

fijxNj ≥ fi

Esta inequacao e o Corte de Gomory.

A aplicacao repetida destes cortes no problema relaxado garante quechegaremos ao ponto otimo inteiro!

Note que a adicao da inequacao implica, naturalmente, em umaumento do tamanho da base do Simplex e em uma variavel de folgaa mais!

Observe tambem que este e um metodo de geracao de linhas!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 12 / 31

Page 27: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Cortes de Gomory

Ou seja:

−∑j∈N

fijxNj ≤ −fi →

∑j∈N

fijxNj ≥ fi

Esta inequacao e o Corte de Gomory.

A aplicacao repetida destes cortes no problema relaxado garante quechegaremos ao ponto otimo inteiro!

Note que a adicao da inequacao implica, naturalmente, em umaumento do tamanho da base do Simplex e em uma variavel de folgaa mais!

Observe tambem que este e um metodo de geracao de linhas!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 12 / 31

Page 28: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Considere o seguinte problema de PI:

Maximizar z = 21x1 + 11x2

Sujeito a: 7x1 + 4x2 ≤ 13x1, x2 ∈ Z≥0

O formato padrao deste problema e:

Maximizar z = 21x1 + 11x2

Sujeito a: 7x1 + 4x2 + x3 = 13x1, x2, x3 ∈ Z≥0

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 13 / 31

Page 29: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Considere o seguinte problema de PI:

Maximizar z = 21x1 + 11x2

Sujeito a: 7x1 + 4x2 ≤ 13x1, x2 ∈ Z≥0

O formato padrao deste problema e:

Maximizar z = 21x1 + 11x2

Sujeito a: 7x1 + 4x2 + x3 = 13x1, x2, x3 ∈ Z≥0

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 13 / 31

Page 30: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Para o mesmo, temos o seguinte quadro Simplex otimo:

BASE x1 x2 x3 b

x1 1 4/7 1/7 13/7

z 0 1 3 39

A solucao otima encontrada nao e inteira!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 14 / 31

Page 31: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Para o mesmo, temos o seguinte quadro Simplex otimo:

BASE x1 x2 x3 b

x1 1 4/7 1/7 13/7

z 0 1 3 39

A solucao otima encontrada nao e inteira!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 14 / 31

Page 32: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Para a linha da unica restricao no quadro, temos:

Variaveis nao-basicas: x2, x3 ∈ Nb1 = 13/7a12 = 4/7a13 = 1/7

O que nos da, de acordo com a formula:

xBi = bi −∑j∈N

aijxNj

A seguinte equacao:

x1 =13

7−(

4

7x2 +

1

7x3

)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 15 / 31

Page 33: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Para a linha da unica restricao no quadro, temos:

Variaveis nao-basicas: x2, x3 ∈ N

b1 = 13/7a12 = 4/7a13 = 1/7

O que nos da, de acordo com a formula:

xBi = bi −∑j∈N

aijxNj

A seguinte equacao:

x1 =13

7−(

4

7x2 +

1

7x3

)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 15 / 31

Page 34: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Para a linha da unica restricao no quadro, temos:

Variaveis nao-basicas: x2, x3 ∈ Nb1 = 13/7

a12 = 4/7a13 = 1/7

O que nos da, de acordo com a formula:

xBi = bi −∑j∈N

aijxNj

A seguinte equacao:

x1 =13

7−(

4

7x2 +

1

7x3

)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 15 / 31

Page 35: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Para a linha da unica restricao no quadro, temos:

Variaveis nao-basicas: x2, x3 ∈ Nb1 = 13/7a12 = 4/7

a13 = 1/7

O que nos da, de acordo com a formula:

xBi = bi −∑j∈N

aijxNj

A seguinte equacao:

x1 =13

7−(

4

7x2 +

1

7x3

)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 15 / 31

Page 36: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Para a linha da unica restricao no quadro, temos:

Variaveis nao-basicas: x2, x3 ∈ Nb1 = 13/7a12 = 4/7a13 = 1/7

O que nos da, de acordo com a formula:

xBi = bi −∑j∈N

aijxNj

A seguinte equacao:

x1 =13

7−(

4

7x2 +

1

7x3

)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 15 / 31

Page 37: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Para a linha da unica restricao no quadro, temos:

Variaveis nao-basicas: x2, x3 ∈ Nb1 = 13/7a12 = 4/7a13 = 1/7

O que nos da, de acordo com a formula:

xBi = bi −∑j∈N

aijxNj

A seguinte equacao:

x1 =13

7−(

4

7x2 +

1

7x3

)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 15 / 31

Page 38: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Para a linha da unica restricao no quadro, temos:

Variaveis nao-basicas: x2, x3 ∈ Nb1 = 13/7a12 = 4/7a13 = 1/7

O que nos da, de acordo com a formula:

xBi = bi −∑j∈N

aijxNj

A seguinte equacao:

x1 =13

7−(

4

7x2 +

1

7x3

)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 15 / 31

Page 39: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Separando as partes inteiras e fracionarias como visto anteriormente,teremos:

x1 = (1− 0x2 − 0x3) +

(6

7− 4

7x2 −

1

7x3

)De onde podemos tirar o seguinte corte:

−4

7x2 −

1

7x3 ≤ −

6

7→ 4

7x2 +

1

7x3 ≥

6

7

Teremos uma nova variavel de folga para manter esta nova restricaono formato padrao:

4

7x2 +

1

7x3 − x4 =

6

7

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 16 / 31

Page 40: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Separando as partes inteiras e fracionarias como visto anteriormente,teremos:

x1 = (1− 0x2 − 0x3) +

(6

7− 4

7x2 −

1

7x3

)

De onde podemos tirar o seguinte corte:

−4

7x2 −

1

7x3 ≤ −

6

7→ 4

7x2 +

1

7x3 ≥

6

7

Teremos uma nova variavel de folga para manter esta nova restricaono formato padrao:

4

7x2 +

1

7x3 − x4 =

6

7

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 16 / 31

Page 41: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Separando as partes inteiras e fracionarias como visto anteriormente,teremos:

x1 = (1− 0x2 − 0x3) +

(6

7− 4

7x2 −

1

7x3

)De onde podemos tirar o seguinte corte:

−4

7x2 −

1

7x3 ≤ −

6

7→ 4

7x2 +

1

7x3 ≥

6

7

Teremos uma nova variavel de folga para manter esta nova restricaono formato padrao:

4

7x2 +

1

7x3 − x4 =

6

7

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 16 / 31

Page 42: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Separando as partes inteiras e fracionarias como visto anteriormente,teremos:

x1 = (1− 0x2 − 0x3) +

(6

7− 4

7x2 −

1

7x3

)De onde podemos tirar o seguinte corte:

−4

7x2 −

1

7x3 ≤ −

6

7→ 4

7x2 +

1

7x3 ≥

6

7

Teremos uma nova variavel de folga para manter esta nova restricaono formato padrao:

4

7x2 +

1

7x3 − x4 =

6

7

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 16 / 31

Page 43: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Reotimizando, o novo quadro otimo Simplex e:

BASE x1 x2 x3 x4 b

x1 1 0 0 1 1x2 0 1 1/4 -7/4 3/2

Z 0 0 11/4 7/4 75/2

O mesmo continua nao sendo otimo!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 17 / 31

Page 44: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Reotimizando, o novo quadro otimo Simplex e:

BASE x1 x2 x3 x4 b

x1 1 0 0 1 1x2 0 1 1/4 -7/4 3/2

Z 0 0 11/4 7/4 75/2

O mesmo continua nao sendo otimo!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 17 / 31

Page 45: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Reotimizando, o novo quadro otimo Simplex e:

BASE x1 x2 x3 x4 b

x1 1 0 0 1 1x2 0 1 1/4 -7/4 3/2

Z 0 0 11/4 7/4 75/2

O mesmo continua nao sendo otimo!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 17 / 31

Page 46: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Olhando para o quadro, temos que:

x2 =3

2−(

1

4x3 −

7

4x4

)

Separando partes inteiras e fracionarias (primeira tentativa):

x2 = 1 +1

2−(

1

4x3 − x4 −

3

4x4

)x2 = [1− (0x3 − x4)] +

[1

2−(

1

4x3 −

1

4x4

)]A parte fracionaria do coeficiente de x4 na equacao nao satisfazfi ≥ 0. Portanto, a mesma nao formara um corte valido.

Observe que −7

4= −2 +

1

4. Neste caso, a parte fracionaria respeita a

restricao.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 18 / 31

Page 47: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Olhando para o quadro, temos que:

x2 =3

2−(

1

4x3 −

7

4x4

)Separando partes inteiras e fracionarias (primeira tentativa):

x2 = 1 +1

2−(

1

4x3 − x4 −

3

4x4

)x2 = [1− (0x3 − x4)] +

[1

2−(

1

4x3 −

1

4x4

)]

A parte fracionaria do coeficiente de x4 na equacao nao satisfazfi ≥ 0. Portanto, a mesma nao formara um corte valido.

Observe que −7

4= −2 +

1

4. Neste caso, a parte fracionaria respeita a

restricao.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 18 / 31

Page 48: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Olhando para o quadro, temos que:

x2 =3

2−(

1

4x3 −

7

4x4

)Separando partes inteiras e fracionarias (primeira tentativa):

x2 = 1 +1

2−(

1

4x3 − x4 −

3

4x4

)x2 = [1− (0x3 − x4)] +

[1

2−(

1

4x3 −

1

4x4

)]A parte fracionaria do coeficiente de x4 na equacao nao satisfazfi ≥ 0. Portanto, a mesma nao formara um corte valido.

Observe que −7

4= −2 +

1

4. Neste caso, a parte fracionaria respeita a

restricao.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 18 / 31

Page 49: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Olhando para o quadro, temos que:

x2 =3

2−(

1

4x3 −

7

4x4

)Separando partes inteiras e fracionarias (primeira tentativa):

x2 = 1 +1

2−(

1

4x3 − x4 −

3

4x4

)x2 = [1− (0x3 − x4)] +

[1

2−(

1

4x3 −

1

4x4

)]A parte fracionaria do coeficiente de x4 na equacao nao satisfazfi ≥ 0. Portanto, a mesma nao formara um corte valido.

Observe que −7

4= −2 +

1

4. Neste caso, a parte fracionaria respeita a

restricao.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 18 / 31

Page 50: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Separando partes inteiras e fracionarias (segunda tentativa):

x2 = 1 +1

2−(

1

4x3 − 2x4 +

1

4x4

)x2 = [1− (0x3 − 2x4)] +

[1

2−(

1

4x3 +

1

4x4

)]x2 = (1− 0x3 + 2x4) +

(1

2− 1

4x3 −

1

4x4

)

Obtemos o corte:

1

4x3 +

1

4x4 − x5 =

1

2Onde x5 e a nova variavel de folga.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 19 / 31

Page 51: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Separando partes inteiras e fracionarias (segunda tentativa):

x2 = 1 +1

2−(

1

4x3 − 2x4 +

1

4x4

)x2 = [1− (0x3 − 2x4)] +

[1

2−(

1

4x3 +

1

4x4

)]x2 = (1− 0x3 + 2x4) +

(1

2− 1

4x3 −

1

4x4

)Obtemos o corte:

1

4x3 +

1

4x4 − x5 =

1

2Onde x5 e a nova variavel de folga.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 19 / 31

Page 52: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Reotimizando mais uma vez, o novo quadro otimo Simplex e:

BASE x1 x2 x3 x4 x5 b

x3 -1 0 1 0 -4 1x2 2 1 0 0 1 3x4 1 0 0 1 0 1

Z 1 0 0 0 11 33

Chegamos a solucao otima inteira, com:

Z* = 33x3* = 1x2* = 3x4* = 1 (folga)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 20 / 31

Page 53: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Reotimizando mais uma vez, o novo quadro otimo Simplex e:

BASE x1 x2 x3 x4 x5 b

x3 -1 0 1 0 -4 1x2 2 1 0 0 1 3x4 1 0 0 1 0 1

Z 1 0 0 0 11 33

Chegamos a solucao otima inteira, com:

Z* = 33x3* = 1x2* = 3x4* = 1 (folga)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 20 / 31

Page 54: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Reotimizando mais uma vez, o novo quadro otimo Simplex e:

BASE x1 x2 x3 x4 x5 b

x3 -1 0 1 0 -4 1x2 2 1 0 0 1 3x4 1 0 0 1 0 1

Z 1 0 0 0 11 33

Chegamos a solucao otima inteira, com:

Z* = 33x3* = 1x2* = 3x4* = 1 (folga)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 20 / 31

Page 55: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Reotimizando mais uma vez, o novo quadro otimo Simplex e:

BASE x1 x2 x3 x4 x5 b

x3 -1 0 1 0 -4 1x2 2 1 0 0 1 3x4 1 0 0 1 0 1

Z 1 0 0 0 11 33

Chegamos a solucao otima inteira, com:

Z* = 33

x3* = 1x2* = 3x4* = 1 (folga)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 20 / 31

Page 56: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Reotimizando mais uma vez, o novo quadro otimo Simplex e:

BASE x1 x2 x3 x4 x5 b

x3 -1 0 1 0 -4 1x2 2 1 0 0 1 3x4 1 0 0 1 0 1

Z 1 0 0 0 11 33

Chegamos a solucao otima inteira, com:

Z* = 33x3* = 1

x2* = 3x4* = 1 (folga)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 20 / 31

Page 57: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Reotimizando mais uma vez, o novo quadro otimo Simplex e:

BASE x1 x2 x3 x4 x5 b

x3 -1 0 1 0 -4 1x2 2 1 0 0 1 3x4 1 0 0 1 0 1

Z 1 0 0 0 11 33

Chegamos a solucao otima inteira, com:

Z* = 33x3* = 1x2* = 3

x4* = 1 (folga)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 20 / 31

Page 58: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Planos de Corte Cortes de Gomory

Exemplo 5: Usando Cortes de Gomory

Reotimizando mais uma vez, o novo quadro otimo Simplex e:

BASE x1 x2 x3 x4 x5 b

x3 -1 0 1 0 -4 1x2 2 1 0 0 1 3x4 1 0 0 1 0 1

Z 1 0 0 0 11 33

Chegamos a solucao otima inteira, com:

Z* = 33x3* = 1x2* = 3x4* = 1 (folga)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 20 / 31

Page 59: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Metodo Branch-and-Cut

O Branch-and-Cut e uma combinacao do Branch-and-Bound com osPlanos de Corte.

Sabemos que ambos sao capazes de encontrar a solucao de umproblema de PI, porem, isso pode levar um longo tempo.

Combinando os dois metodos, podemos diminuir este tempo!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 21 / 31

Page 60: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Metodo Branch-and-Cut

O Branch-and-Cut e uma combinacao do Branch-and-Bound com osPlanos de Corte.

Sabemos que ambos sao capazes de encontrar a solucao de umproblema de PI, porem, isso pode levar um longo tempo.

Combinando os dois metodos, podemos diminuir este tempo!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 21 / 31

Page 61: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Metodo Branch-and-Cut

O Branch-and-Cut e uma combinacao do Branch-and-Bound com osPlanos de Corte.

Sabemos que ambos sao capazes de encontrar a solucao de umproblema de PI, porem, isso pode levar um longo tempo.

Combinando os dois metodos, podemos diminuir este tempo!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 21 / 31

Page 62: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Metodo Branch-and-Cut

A cada no da arvore de branch-and-bound, pode-se aplicar ummetodo de corte no subproblema, sendo controlado por algumcriterio, por exemplo:

Realizar n cortes de Gomory por no;Adicionar inequacoes especıficas do problema original;Efetuar cortes a cada nıvel da arvore que seja multiplo de algum valor.

Metodos de Branch-and-Cut costumam ser bastante eficientes, noentanto, as melhores aplicacoes do mesmo usam restricoes especıficasdo problema atacado.

Lembrando, por exemplo, das restricoes de eliminacao de subrota doCaixeiro Viajante.

Quando os cortes sao feitos apenas na raiz da arvore deenumeracao, o metodo e chamado de Cut-and-Branch.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 22 / 31

Page 63: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Metodo Branch-and-Cut

A cada no da arvore de branch-and-bound, pode-se aplicar ummetodo de corte no subproblema, sendo controlado por algumcriterio, por exemplo:

Realizar n cortes de Gomory por no;

Adicionar inequacoes especıficas do problema original;Efetuar cortes a cada nıvel da arvore que seja multiplo de algum valor.

Metodos de Branch-and-Cut costumam ser bastante eficientes, noentanto, as melhores aplicacoes do mesmo usam restricoes especıficasdo problema atacado.

Lembrando, por exemplo, das restricoes de eliminacao de subrota doCaixeiro Viajante.

Quando os cortes sao feitos apenas na raiz da arvore deenumeracao, o metodo e chamado de Cut-and-Branch.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 22 / 31

Page 64: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Metodo Branch-and-Cut

A cada no da arvore de branch-and-bound, pode-se aplicar ummetodo de corte no subproblema, sendo controlado por algumcriterio, por exemplo:

Realizar n cortes de Gomory por no;Adicionar inequacoes especıficas do problema original;

Efetuar cortes a cada nıvel da arvore que seja multiplo de algum valor.

Metodos de Branch-and-Cut costumam ser bastante eficientes, noentanto, as melhores aplicacoes do mesmo usam restricoes especıficasdo problema atacado.

Lembrando, por exemplo, das restricoes de eliminacao de subrota doCaixeiro Viajante.

Quando os cortes sao feitos apenas na raiz da arvore deenumeracao, o metodo e chamado de Cut-and-Branch.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 22 / 31

Page 65: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Metodo Branch-and-Cut

A cada no da arvore de branch-and-bound, pode-se aplicar ummetodo de corte no subproblema, sendo controlado por algumcriterio, por exemplo:

Realizar n cortes de Gomory por no;Adicionar inequacoes especıficas do problema original;Efetuar cortes a cada nıvel da arvore que seja multiplo de algum valor.

Metodos de Branch-and-Cut costumam ser bastante eficientes, noentanto, as melhores aplicacoes do mesmo usam restricoes especıficasdo problema atacado.

Lembrando, por exemplo, das restricoes de eliminacao de subrota doCaixeiro Viajante.

Quando os cortes sao feitos apenas na raiz da arvore deenumeracao, o metodo e chamado de Cut-and-Branch.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 22 / 31

Page 66: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Metodo Branch-and-Cut

A cada no da arvore de branch-and-bound, pode-se aplicar ummetodo de corte no subproblema, sendo controlado por algumcriterio, por exemplo:

Realizar n cortes de Gomory por no;Adicionar inequacoes especıficas do problema original;Efetuar cortes a cada nıvel da arvore que seja multiplo de algum valor.

Metodos de Branch-and-Cut costumam ser bastante eficientes, noentanto, as melhores aplicacoes do mesmo usam restricoes especıficasdo problema atacado.

Lembrando, por exemplo, das restricoes de eliminacao de subrota doCaixeiro Viajante.

Quando os cortes sao feitos apenas na raiz da arvore deenumeracao, o metodo e chamado de Cut-and-Branch.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 22 / 31

Page 67: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Metodo Branch-and-Cut

A cada no da arvore de branch-and-bound, pode-se aplicar ummetodo de corte no subproblema, sendo controlado por algumcriterio, por exemplo:

Realizar n cortes de Gomory por no;Adicionar inequacoes especıficas do problema original;Efetuar cortes a cada nıvel da arvore que seja multiplo de algum valor.

Metodos de Branch-and-Cut costumam ser bastante eficientes, noentanto, as melhores aplicacoes do mesmo usam restricoes especıficasdo problema atacado.

Lembrando, por exemplo, das restricoes de eliminacao de subrota doCaixeiro Viajante.

Quando os cortes sao feitos apenas na raiz da arvore deenumeracao, o metodo e chamado de Cut-and-Branch.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 22 / 31

Page 68: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Metodo Branch-and-Cut

A cada no da arvore de branch-and-bound, pode-se aplicar ummetodo de corte no subproblema, sendo controlado por algumcriterio, por exemplo:

Realizar n cortes de Gomory por no;Adicionar inequacoes especıficas do problema original;Efetuar cortes a cada nıvel da arvore que seja multiplo de algum valor.

Metodos de Branch-and-Cut costumam ser bastante eficientes, noentanto, as melhores aplicacoes do mesmo usam restricoes especıficasdo problema atacado.

Lembrando, por exemplo, das restricoes de eliminacao de subrota doCaixeiro Viajante.

Quando os cortes sao feitos apenas na raiz da arvore deenumeracao, o metodo e chamado de Cut-and-Branch.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 22 / 31

Page 69: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

Considere o seguinte problema de PI:

Maximizar z = 6x1 + 5x2

Sujeito a:3x1 + x2 ≤ 11−x1 + 2x2 ≤ 5x1, x2 ∈ Z≥0

Nosso primeiro passo sera resolver a relaxacao contınua desteproblema, que nos dara a solucao:

x1 =17

7= 2, 4285; x2 =

26

7= 3, 7142 e z =

232

7= 33, 1428.

Agora, devemos decidir: usaremos um plano de corte ou efetuaremosuma operacao de branching?

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 23 / 31

Page 70: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

Considere o seguinte problema de PI:

Maximizar z = 6x1 + 5x2

Sujeito a:3x1 + x2 ≤ 11−x1 + 2x2 ≤ 5x1, x2 ∈ Z≥0

Nosso primeiro passo sera resolver a relaxacao contınua desteproblema, que nos dara a solucao:

x1 =17

7= 2, 4285; x2 =

26

7= 3, 7142 e z =

232

7= 33, 1428.

Agora, devemos decidir: usaremos um plano de corte ou efetuaremosuma operacao de branching?

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 23 / 31

Page 71: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

Considere o seguinte problema de PI:

Maximizar z = 6x1 + 5x2

Sujeito a:3x1 + x2 ≤ 11−x1 + 2x2 ≤ 5x1, x2 ∈ Z≥0

Nosso primeiro passo sera resolver a relaxacao contınua desteproblema, que nos dara a solucao:

x1 =17

7= 2, 4285; x2 =

26

7= 3, 7142 e z =

232

7= 33, 1428.

Agora, devemos decidir: usaremos um plano de corte ou efetuaremosuma operacao de branching?

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 23 / 31

Page 72: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

Se efetuarmos uma operacao de branching na variavel

x1 =17

7= 2, 43, teremos os seguintes subproblemas:

P1: Maximizar z = 6x1 + 5x2

Sujeito a:3x1 + x2 ≤ 11−x1 + 2x2 ≤ 5x1 ≥ 3x1, x2 ∈ Z≥0

P2: Maximizar z = 6x1 + 5x2

Sujeito a:3x1 + x2 ≤ 11−x1 + 2x2 ≤ 5x1 ≤ 2x1, x2 ∈ Z≥0

A solucao do nosso problema sera a melhor dentre a de cada um dossubproblemas (como o problema e de maximizacao, sera a maior).

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 24 / 31

Page 73: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

Se efetuarmos uma operacao de branching na variavel

x1 =17

7= 2, 43, teremos os seguintes subproblemas:

P1: Maximizar z = 6x1 + 5x2

Sujeito a:3x1 + x2 ≤ 11−x1 + 2x2 ≤ 5x1 ≥ 3x1, x2 ∈ Z≥0

P2: Maximizar z = 6x1 + 5x2

Sujeito a:3x1 + x2 ≤ 11−x1 + 2x2 ≤ 5x1 ≤ 2x1, x2 ∈ Z≥0

A solucao do nosso problema sera a melhor dentre a de cada um dossubproblemas (como o problema e de maximizacao, sera a maior).

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 24 / 31

Page 74: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

Se efetuarmos uma operacao de branching na variavel

x1 =17

7= 2, 43, teremos os seguintes subproblemas:

P1: Maximizar z = 6x1 + 5x2

Sujeito a:3x1 + x2 ≤ 11−x1 + 2x2 ≤ 5x1 ≥ 3x1, x2 ∈ Z≥0

P2: Maximizar z = 6x1 + 5x2

Sujeito a:3x1 + x2 ≤ 11−x1 + 2x2 ≤ 5x1 ≤ 2x1, x2 ∈ Z≥0

A solucao do nosso problema sera a melhor dentre a de cada um dossubproblemas (como o problema e de maximizacao, sera a maior).

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 24 / 31

Page 75: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

A solucao de P1 e x1 = 3, x2 = 2, com z = 28. Esta solucao e inteira,entao, ela se torna a nossa primeira solucao incumbente (ou seja,passa a ser nosso limite inferior!). Este no, portanto, sera podado.

A solucao de P2 e x1 = 2 e x2 = 3, 5, com z = 29, 5. Esta solucao efracionaria e e maior que nosso limite inferior, logo, ainda hapotencial para melhora!

Neste ponto, assuma que o algoritmo usara um plano de corte(podemos considerar que ele usara plano de corte quando houverapenas uma variavel fracionaria ou a cada nıvel da arvore).

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 25 / 31

Page 76: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

A solucao de P1 e x1 = 3, x2 = 2, com z = 28. Esta solucao e inteira,entao, ela se torna a nossa primeira solucao incumbente (ou seja,passa a ser nosso limite inferior!). Este no, portanto, sera podado.

A solucao de P2 e x1 = 2 e x2 = 3, 5, com z = 29, 5. Esta solucao efracionaria e e maior que nosso limite inferior, logo, ainda hapotencial para melhora!

Neste ponto, assuma que o algoritmo usara um plano de corte(podemos considerar que ele usara plano de corte quando houverapenas uma variavel fracionaria ou a cada nıvel da arvore).

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 25 / 31

Page 77: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

A solucao de P1 e x1 = 3, x2 = 2, com z = 28. Esta solucao e inteira,entao, ela se torna a nossa primeira solucao incumbente (ou seja,passa a ser nosso limite inferior!). Este no, portanto, sera podado.

A solucao de P2 e x1 = 2 e x2 = 3, 5, com z = 29, 5. Esta solucao efracionaria e e maior que nosso limite inferior, logo, ainda hapotencial para melhora!

Neste ponto, assuma que o algoritmo usara um plano de corte(podemos considerar que ele usara plano de corte quando houverapenas uma variavel fracionaria ou a cada nıvel da arvore).

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 25 / 31

Page 78: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

O quadro simplex otimo de P2 e:

BASE x1 x2 x3 x4 x5 b

x3 0 0 1 -1/2 -7/2 3/2x2 0 1 0 1/2 1/2 7/2x1 1 0 0 0 1 2

Z 0 0 0 5/2 17/2 59/2

A variavel x2 nao e inteira, logo, a linha da mesma gerara um corte deGomory.

Tem-se:

x2 +1

2x4 +

1

2x5 =

7

2→ x2 =

7

2−(

1

2x4 +

1

2x5

)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 26 / 31

Page 79: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

O quadro simplex otimo de P2 e:

BASE x1 x2 x3 x4 x5 b

x3 0 0 1 -1/2 -7/2 3/2x2 0 1 0 1/2 1/2 7/2x1 1 0 0 0 1 2

Z 0 0 0 5/2 17/2 59/2

A variavel x2 nao e inteira, logo, a linha da mesma gerara um corte deGomory.

Tem-se:

x2 +1

2x4 +

1

2x5 =

7

2→ x2 =

7

2−(

1

2x4 +

1

2x5

)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 26 / 31

Page 80: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

O quadro simplex otimo de P2 e:

BASE x1 x2 x3 x4 x5 b

x3 0 0 1 -1/2 -7/2 3/2x2 0 1 0 1/2 1/2 7/2x1 1 0 0 0 1 2

Z 0 0 0 5/2 17/2 59/2

A variavel x2 nao e inteira, logo, a linha da mesma gerara um corte deGomory.

Tem-se:

x2 +1

2x4 +

1

2x5 =

7

2→ x2 =

7

2−(

1

2x4 +

1

2x5

)

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 26 / 31

Page 81: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

Separando partes inteiras e fracionarias:

x2 =7

2−(

1

2x4 +

1

2x5

)→

x2 = [3− (0x4 − 0x5)] +

[1

2−(

1

2x4 +

1

2x5

)]x2 = (3− 0x3 + 0x4) +

(1

2− 1

2x4 −

1

2x5

)

Obtemos o corte:

1

2− 1

2x4−

1

2x5 ≤ 0 → 1

2x4 +

1

2x5 ≥

1

2→

1

2x4 +

1

2x5− x6 =

1

2

Onde x6 e a nova variavel de folga.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 27 / 31

Page 82: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

Separando partes inteiras e fracionarias:

x2 =7

2−(

1

2x4 +

1

2x5

)→

x2 = [3− (0x4 − 0x5)] +

[1

2−(

1

2x4 +

1

2x5

)]x2 = (3− 0x3 + 0x4) +

(1

2− 1

2x4 −

1

2x5

)Obtemos o corte:

1

2− 1

2x4−

1

2x5 ≤ 0 → 1

2x4 +

1

2x5 ≥

1

2→

1

2x4 +

1

2x5− x6 =

1

2

Onde x6 e a nova variavel de folga.

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 27 / 31

Page 83: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

Esta inequacao sera o nosso plano de corte, nos fornecendo o novoproblema P3:

P3: Maximizar z = 6x1 + 5x2

Sujeito a:3x1 + x2 ≤ 11−x1 + 2x2 ≤ 5x2 ≤ 21

2x4 +

1

2x5 − x6 =

1

2x1, x2 ∈ Z≥0

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 28 / 31

Page 84: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

A solucao de P3 e x1 = 2, x2 = 3, com z = 27. Esta solucao e inteira,logo, o no sera podado.

A nova solucao inteira e pior que a incumbente atual (melhor inteiraencontrada), logo, sera descartada!

Nao temos mais nos para serem podados, logo, a solucao otima doproblema de PI e x1 = 3, x2 = 2, com z = 28!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 29 / 31

Page 85: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

A solucao de P3 e x1 = 2, x2 = 3, com z = 27. Esta solucao e inteira,logo, o no sera podado.

A nova solucao inteira e pior que a incumbente atual (melhor inteiraencontrada), logo, sera descartada!

Nao temos mais nos para serem podados, logo, a solucao otima doproblema de PI e x1 = 3, x2 = 2, com z = 28!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 29 / 31

Page 86: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

A solucao de P3 e x1 = 2, x2 = 3, com z = 27. Esta solucao e inteira,logo, o no sera podado.

A nova solucao inteira e pior que a incumbente atual (melhor inteiraencontrada), logo, sera descartada!

Nao temos mais nos para serem podados, logo, a solucao otima doproblema de PI e x1 = 3, x2 = 2, com z = 28!

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 29 / 31

Page 87: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Branch-and-Cut

Exemplo 6: Branch-and-Cut (corte aplicado em branch-and-bound)

P0

x1 = 2,4285x2 = 3,7142z = 33,1428

x1 ≥ 3 x1 ≤ 2

P1

x1 = 3x2 = 2z = 28

P2

x1 = 2x2 = 3,5z = 29,5

IncumbenteSolução ótima

P3

x1 = 2x2 = 3z = 27

Adicionar corte:1/2 x4 + 1/2 x5 - x6 = 1/2

IncumbenteDescartada

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 30 / 31

Page 88: Introdu˘c~ao a Otimiza˘c~ao Combinat oriaioc-ufam.weebly.com/.../ioc201501-planoscorte-branchandcut.pdf · Planos de Corte Ideia para pensar Como visto no m etodo branch-and-bound,

Referencias

Referencias

PAPADIMITRIOU, Christos. STEIGLITZ, Kenneth. Combinatorial Optimization -Algorithms and Complexity. Dover, 1998.

TRICK, Michael. Branch-and-Bound. Carnegie Mellon University. Disponıvel emhttp://mat.gsia.cmu.edu/orclass/integer/node13.html

PIZZOLATO, Nelio Domingues. GANDOLPHO, Andre Alves. Tecnicas deOtimizacao. Livros Tecnicos e Cientıficos, 2009.

RODRIGUES, Rosiane de Freitas. Notas de Aula de Otimizacao Combinatoria -Branch-and-Bound. Universidade Federal do Amazonas, 2010.

SANTOS, Haroldo. Notas de Aula de Algoritmos e Estruturas de Dados III -Branch-and-Bound. Universidade Federal de Ouro Preto, 2009.

LETCHFORD, Adam N.. An Introduction to Branch-and-Cut - Part I: PolyhedralTheory. Lancaster University, 2011.

MITCHELL, John E.. Branch-and-Cut Algorithms for Combinatorial OptimizationProblems. Rensselaer Polytechnic Institute, 1999.

Vertex Cover. Wikipedia, the free encyclopedia. Disponıvel emhttp://en.wikipedia.org/wiki/Vertex_cover

Rosiane de Freitas (IComp/UFAM) Branch-and-Bound Maio de 2015 31 / 31