View
231
Download
0
Category
Preview:
Citation preview
Introducao a Otimizacao CombinatoriaMetodos Exatos para PI - Parte 2: Planos de Corte e
Branch-and-Cut
Professora:
Rosiane de Freitas(rosiane@icomp.ufam.edu.br)
Bruno Raphael Cardoso Dias
Prof. Estagio em Docencia
(bruno.dias@icomp.ufam.edu.br)
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Recommended