Buscar

Slides_BranchandBound

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 3, do total de 51 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 6, do total de 51 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 9, do total de 51 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Prévia do material em texto

Introduc¸a˜o a` Programac¸a˜o Linear Inteira Mista
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG
Departamento de Engenharia de Produc¸a˜o EE UFMG
carlos@dep.ufmg.br
28 de junho de 2011
Programac¸a˜o Inteira
Introduc¸a˜o
Definic¸a˜o
Te´cnica branch-and-baund
Algoritmo branch-and-baund
Programac¸a˜o Linear Bina´ria
Definic¸a˜o
Algoritmo branch-and-bound para PLIB - Balas [1]
Programac¸a˜o Linear Inteira Mista
Definic¸a˜o
Algoritmo branch-and-bound para PLIM
Bibliografia
Um problema inteiro
O problema de sequ¨enciamento em uma ma´quina 1|ri , d˜i |Cmax
Job J1 J2 J3 J4
ri 4 1 1 0
pi 2 1 2 2
d˜i 7 5 6 4
Uma a´rvore branch-and-baund
+r1 1p(T1 /)1v
v 21
+r1 p1
( 1 T T2
r
, /)
max{ +p22},
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���
���
���
���
���
���
���
���
���
���
���
���
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
���
���
���
���
���
���
���
���
���
���
���
���
raiz
)/(T p+r2 2 2 )/ p(T +rn n n. . .v v2 n
1v 1v3 n
. . .
, }+p
)/,
r
TT( 1 
1p1 max{ +r , }+p
)/,
max{ r
T( 1 T
1p1 +r
3
3 3
n
n n
Um problema inteiro
O problema de sequ¨enciamento em uma ma´quina 1|ri , d˜i |Cmax
Job J1 J2 J3 J4
ri 4 1 1 0
pi 2 1 2 2
d˜i 7 5 6 4
Uma a´rvore branch-and-baund
+r1 1p(T1 /)1v
v 21
+r1 p1
( 1 T T2
r
, /)
max{ +p22},
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
�����
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
��������
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���������������
���
���
���
���
���
���
���
���
���
���
���
���
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
���
���
���
���
���
���
���
���
���
���
���
���
raiz
)/(T p+r2 2 2 )/ p(T +rn n n. . .v v2 n
1v 1v3 n
. . .
, }+p
)/,
r
TT( 1 
1p1 max{ +r , }+p
)/,
max{ r
T( 1 T
1p1 +r
3
3 3
n
n n
Definic¸a˜o
Programac¸a˜o Linear Inteira
minimizar z =
n∑
j=1
cjxj
sujeito a`
n∑
j=1
aijxj ≥ bi ∀i = 1, . . . , n
xi ∈ IN ∀j = 1, . . . , n.
Caracter´ısticas do problema
I a func¸a˜o objetivo e´ linear;
I todas as restric¸o˜es sa˜o lineares;
I todas as varia´veis sa˜o inteiras (∈ IN).
Definic¸a˜o
Programac¸a˜o Linear Inteira
minimizar z =
n∑
j=1
cjxj
sujeito a`
n∑
j=1
aijxj ≥ bi ∀i = 1, . . . , n
xi ∈ IN ∀j = 1, . . . , n.
Caracter´ısticas do problema
I a func¸a˜o objetivo e´ linear;
I todas as restric¸o˜es sa˜o lineares;
I todas as varia´veis sa˜o inteiras (∈ IN).
Definic¸a˜o
Programac¸a˜o Linear Inteira
minimizar z =
n∑
j=1
cjxj
sujeito a`
n∑
j=1
aijxj ≥ bi ∀i = 1, . . . , n
xi ∈ IN ∀j = 1, . . . , n.
Caracter´ısticas do problema
I a func¸a˜o objetivo e´ linear;
I todas as restric¸o˜es sa˜o lineares;
I todas as varia´veis sa˜o inteiras (∈ IN).
Definic¸a˜o
Programac¸a˜o Linear Inteira
minimizar z =
n∑
j=1
cjxj
sujeito a`
n∑
j=1
aijxj ≥ bi ∀i = 1, . . . , n
xi ∈ IN ∀j = 1, . . . , n.
Caracter´ısticas do problema
I a func¸a˜o objetivo e´ linear;
I todas as restric¸o˜es sa˜o lineares;
I todas as varia´veis sa˜o inteiras (∈ IN).
Definic¸a˜o
Programac¸a˜o Linear Inteira
minimizar z =
n∑
j=1
cjxj
sujeito a`
n∑
j=1
aijxj ≥ bi ∀i = 1, . . . , n
xi ∈ IN ∀j = 1, . . . , n.
Caracter´ısticas do problema
I a func¸a˜o objetivo e´ linear;
I todas as restric¸o˜es sa˜o lineares;
I todasas varia´veis sa˜o inteiras (∈ IN).
Dificuldades no arredondamento - 1
a viabilidade na˜o e´ mantida
maximizar z = x1 + 2x2
sujeito a` −x1 + x2 ≤ 2, 5
x1 + x2 ≤ 3, 5
x1 ∈ IN x2 ∈ IN
I o´timo cont´ınuo:
x1 = 0, 5; x2 = 3 e z = 6, 5
I o´timo inteiro:
x1 = 1; x2 = 2 e z = 5
Dificuldades no arredondamento - 1
a viabilidade na˜o e´ mantida
maximizar z = x1 + 2x2
sujeito a` −x1 + x2 ≤ 2, 5
x1 + x2 ≤ 3, 5
x1 ∈ IN x2 ∈ IN
I o´timo cont´ınuo:
x1 = 0, 5; x2 = 3 e z = 6, 5
I o´timo inteiro:
x1 = 1; x2 = 2 e z = 5
Dificuldades no arredondamento - 2
o´timo inteiro longe do o´timo arredondado
maximizar z = x1 + 5x2
sujeito a` x1 + 10x2 ≤ 20
x1 ≤ 2
x1 ∈ IN x2 ∈ IN
I o´timo cont´ınuo:
x1 = 2; x2 = 9/5 e z = 11
I o´timo inteiro:
x1 = 0; x2 = 2 e z = 10
Dificuldades no arredondamento - 2
o´timo inteiro longe do o´timo arredondado
maximizar z = x1 + 5x2
sujeito a` x1 + 10x2 ≤ 20
x1 ≤ 2
x1 ∈ IN x2 ∈ IN
I o´timo cont´ınuo:
x1 = 2; x2 = 9/5 e z = 11
I o´timo inteiro:
x1 = 0; x2 = 2 e z = 10
Construc¸a˜o de uma a´rvore de pesquisa
Caracter´ısticas dos ve´rtices da a´rvore
I ve´rtice aberto
I ve´rtice fechado
I limite superior (LSk)
I limite inferior (LIk)
I Subconjunto de soluc¸o˜es (Sk)
Construc¸a˜o do algoritmo
I LA: lista de ve´rtices aberto
I LF : lista de ve´rtices fechado
I LS : limite superior do problema
I LI : limite inferior do problema
Construc¸a˜o de uma a´rvore de pesquisa
Caracter´ısticas dos ve´rtices da a´rvore
I ve´rtice aberto
I ve´rtice fechado
I limite superior (LSk)
I limite inferior (LIk)
I Subconjunto de soluc¸o˜es (Sk)
Construc¸a˜o do algoritmo
I LA: lista de ve´rtices aberto
I LF : lista de ve´rtices fechado
I LS : limite superior do problema
I LI : limite inferior do problema
Inicializac¸a˜o
Fac¸a:
1. LA = {0}: colocar o ve´rice 0 na lista aberto;
2. LF = ∅: lista fechado e´ vazia;
3. LS = LS0 =∞; LI0 = 0;
4. LI = 0 ou calculado pelas caracter´ısticas do problema;
5. S0 = conjunto de todo o universo de valores para as varia´veis.
Isto inclui as soluc¸o˜es na˜o via´veis do problema;
6. s = ∅ melhor soluc¸a˜o encontrada;
Inicializac¸a˜o
Fac¸a:
1. LA = {0}: colocar o ve´rice 0 na lista aberto;
2. LF = ∅: lista fechado e´ vazia;
3. LS = LS0 =∞; LI0 = 0;
4. LI = 0 ou calculado pelas caracter´ısticas do problema;
5. S0 = conjunto de todo o universo de valores para as varia´veis.
Isto inclui as soluc¸o˜es na˜o via´veis do problema;
6. s = ∅ melhor soluc¸a˜o encontrada;
Inicializac¸a˜o
Fac¸a:
1. LA = {0}: colocar o ve´rice 0 na lista aberto;
2. LF = ∅: lista fechado e´ vazia;
3. LS = LS0 =∞; LI0 = 0;
4. LI = 0 ou calculado pelas caracter´ısticas do problema;
5. S0 = conjunto de todo o universo de valores para as varia´veis.
Isto inclui as soluc¸o˜es na˜o via´veis do problema;
6. s = ∅ melhor soluc¸a˜o encontrada;
Inicializac¸a˜o
Fac¸a:
1. LA = {0}: colocar o ve´rice 0 na lista aberto;
2. LF = ∅: lista fechado e´ vazia;
3. LS = LS0 =∞; LI0 = 0;
4. LI = 0 ou calculado pelas caracter´ısticas do problema;
5. S0 = conjunto de todo o universo de valores para as varia´veis.
Isto inclui as soluc¸o˜es na˜o via´veis do problema;
6. s = ∅ melhor soluc¸a˜o encontrada;
Inicializac¸a˜o
Fac¸a:
1. LA = {0}: colocar o ve´rice 0 na lista aberto;
2. LF = ∅: lista fechado e´ vazia;
3. LS = LS0 =∞; LI0 = 0;
4. LI = 0 ou calculado pelas caracter´ısticas do problema;
5. S0 = conjunto de todo o universo de valores para as varia´veis.
Isto inclui as soluc¸o˜es na˜o via´veis do problema;
6. s = ∅ melhor soluc¸a˜o encontrada;
Inicializac¸a˜o
Fac¸a:
1. LA = {0}: colocar o ve´rice 0 na lista aberto;
2. LF = ∅: lista fechado e´ vazia;
3. LS = LS0 =∞; LI0 = 0;
4. LI = 0 ou calculado pelas caracter´ısticas do problema;
5. S0 = conjunto de todo o universo de valores para as varia´veis.
Isto inclui as soluc¸o˜es na˜o via´veis do problema;
6. s = ∅ melhor soluc¸a˜o encontrada;
Regra de parada
teste
I se LI ≥ LS ou LA = ∅: PARE
I se s = ∅: o problema na˜o tem soluc¸a˜o;
I sena˜o: s e´ a soluc¸a˜o o´tima;
I sena˜o: va´ para iterac¸a˜o;
Regra de parada
teste
I se LI ≥ LS ou LA = ∅: PARE
I se s = ∅: o problema na˜o tem soluc¸a˜o;
I sena˜o: s e´ a soluc¸a˜o o´tima;
I sena˜o: va´ para iterac¸a˜o;
Iterac¸a˜o - primeira parte
branch
Na lista aberto LA, selecione um ve´rtice k (por exemplo, o ve´ritice
de menor limite inferior LIk , neste caso, fac¸a LI = max{LI , LIk});
1. retire o ve´rtice k de LA e coloque-o em LF ;
2. utilizando uma regra apropriada, subdivida o subconjunto Sk
de soluc¸o˜es representadas pelo ve´rtice k em novos
subconjuntos Sk ′ gerando assim os novos ve´rtices k
′ para a
a´rvore de pesquisa;
Iterac¸a˜o - primeira parte
branch
Na lista aberto LA, selecione um ve´rtice k (por exemplo, o ve´ritice
de menor limite inferior LIk , neste caso, fac¸a LI = max{LI , LIk});
1. retire o ve´rtice k de LA e coloque-o em LF ;
2. utilizando uma regra apropriada, subdivida o subconjunto Sk
de soluc¸o˜es representadas pelo ve´rtice k em novos
subconjuntos Sk ′ gerando assim os novos ve´rtices k
′ para a
a´rvore de pesquisa;
Iterac¸a˜o - segunda parte
bound
Para cada novo ve´ritice k ′ gerado, verifique se existe a
possibilidade de soluc¸o˜es via´veis no ve´rtice;
I se sim:
1. calcule o limite inferior LIk′ do ve´rtice;
2. verifique se LIk′ < LS
I se sim: verifique se uma soluc¸a˜o via´vel foi encontrada;
- se sim:
(i) s = nova soluc¸a˜o encontrada;
(ii) LS = LIk′ ;
(iii) transferir todos os ve´rtices k ′′ de LA cujo LIk′′ ≥ LS para
LF ;
- sena˜o: colocar o ve´rtice na LA;
I sena˜o: colocar o ve´rtice k ′ na LF ;
I sena˜o: colocar o ve´rtice k ′ na lista fechado LF ;
Iterac¸a˜o - segunda parte
bound
Para cada novo ve´ritice k ′ gerado, verifique se existe a
possibilidade de soluc¸o˜es via´veis no ve´rtice;
I se sim:
1. calcule o limite inferior LIk′ do ve´rtice;
2. verifique se LIk′ < LS
I se sim: verifique se uma soluc¸a˜o via´vel foi encontrada;
- se sim:
(i) s = nova soluc¸a˜o encontrada;
(ii) LS = LIk′ ;
(iii) transferir todos os ve´rtices k ′′ de LA cujo LIk′′ ≥ LS para
LF ;
- sena˜o: colocar o ve´rtice na LA;
I sena˜o: colocar o ve´rtice k ′ na LF ;
I sena˜o: colocar o ve´rtice k ′ na lista fechado LF ;
Iterac¸a˜o - segunda parte
bound
Para cada novo ve´ritice k ′ gerado, verifique se existe a
possibilidade de soluc¸o˜es via´veis no ve´rtice;
I se sim:
1. calcule o limite inferior LIk′ do ve´rtice;
2. verifique se LIk′ < LS
I se sim: verifique se uma soluc¸a˜o via´vel foi encontrada;
- se sim:
(i) s = nova soluc¸a˜o encontrada;
(ii) LS = LIk′ ;
(iii) transferir todos os ve´rtices k ′′ de LA cujo LIk′′ ≥ LS para
LF ;
- sena˜o: colocar o ve´rtice na LA;
I sena˜o: colocar o ve´rtice k ′ na LF ;
I sena˜o: colocar o ve´rtice k ′ na lista fechado LF ;
Iterac¸a˜o - segunda parte
bound
Para cada novo ve´ritice k ′ gerado, verifique se existe a
possibilidade de soluc¸o˜es via´veis no ve´rtice;
I se sim:
1. calcule o limite inferior LIk′ do ve´rtice;
2. verifique se LIk′ < LS
I se sim: verifique se uma soluc¸a˜o via´vel foi encontrada;
- se sim:
(i) s = nova soluc¸a˜o encontrada;
(ii) LS = LIk′ ;
(iii) transferir todos os ve´rtices k ′′ de LA cujo LIk′′ ≥ LS para
LF ;
- sena˜o: colocar o ve´rtice na LA;
I sena˜o: colocar o ve´rtice k ′ na LF ;
I sena˜o: colocar o ve´rtice k ′ na lista fechado LF ;
Iterac¸a˜o - segunda parte
bound
Para cada novo ve´ritice k ′ gerado, verifique se existe a
possibilidade de soluc¸o˜es via´veis no ve´rtice;
I se sim:
1. calcule o limite inferior LIk′ do ve´rtice;
2. verifique se LIk′ < LS
I se sim: verifique se uma soluc¸a˜o via´vel foi encontrada;
- se sim:
(i) s = nova soluc¸a˜o encontrada;
(ii) LS = LIk′ ;
(iii) transferir todos os ve´rtices k ′′ de LA cujo LIk′′ ≥ LS para
LF ;
- sena˜o: colocar o ve´rtice na LA;
I sena˜o: colocar o ve´rtice k ′ na LF ;
I sena˜o: colocar o ve´rtice k ′ na lista fechado LF ;
Iterac¸a˜o - segunda parte
bound
Para cada novo ve´ritice k ′ gerado, verifique se existe a
possibilidade de soluc¸o˜es via´veis no ve´rtice;I se sim:
1. calcule o limite inferior LIk′ do ve´rtice;
2. verifique se LIk′ < LS
I se sim: verifique se uma soluc¸a˜o via´vel foi encontrada;
- se sim:
(i) s = nova soluc¸a˜o encontrada;
(ii) LS = LIk′ ;
(iii) transferir todos os ve´rtices k ′′ de LA cujo LIk′′ ≥ LS para
LF ;
- sena˜o: colocar o ve´rtice na LA;
I sena˜o: colocar o ve´rtice k ′ na LF ;
I sena˜o: colocar o ve´rtice k ′ na lista fechado LF ;
Observac¸o˜es
performace de um algoritmo branch-and-bound
1. branch: uma maneira eficiente de selecionar o ve´rtice para
dividir o seu subconjunto
2. bound: uma maneira de se obter uma bom limite inferior
maneiras principais para selecionar um ve´ritice
1. pelo menor limite inferior
2. pela largura da a´rvore
3. pela profundidade da a´rvore
Observac¸o˜es
performace de um algoritmo branch-and-bound
1. branch: uma maneira eficiente de selecionar o ve´rtice para
dividir o seu subconjunto
2. bound: uma maneira de se obter uma bom limite inferior
maneiras principais para selecionar um ve´ritice
1. pelo menor limite inferior
2. pela largura da a´rvore
3. pela profundidade da a´rvore
Observac¸o˜es
performace de um algoritmo branch-and-bound
1. branch: uma maneira eficiente de selecionar o ve´rtice para
dividir o seu subconjunto
2. bound: uma maneira de se obter uma bom limite inferior
maneiras principais para selecionar um ve´ritice
1. pelo menor limite inferior
2. pela largura da a´rvore
3. pela profundidade da a´rvore
Observac¸o˜es
performace de um algoritmo branch-and-bound
1. branch: uma maneira eficiente de selecionar o ve´rtice para
dividir o seu subconjunto
2. bound: uma maneira de se obter uma bom limite inferior
maneiras principais para selecionar um ve´ritice
1. pelo menor limite inferior
2. pela largura da a´rvore
3. pela profundidade da a´rvore
Observac¸o˜es
performace de um algoritmo branch-and-bound
1. branch: uma maneira eficiente de selecionar o ve´rtice para
dividir o seu subconjunto
2. bound: uma maneira de se obter uma bom limite inferior
maneiras principais para selecionar um ve´ritice
1. pelo menor limite inferior
2. pela largura da a´rvore
3. pela profundidade da a´rvore
Observac¸o˜es
performace de um algoritmo branch-and-bound
1. branch: uma maneira eficiente de selecionar o ve´rtice para
dividir o seu subconjunto
2. bound: uma maneira de se obter uma bom limite inferior
maneiras principais para selecionar um ve´ritice
1. pelo menor limite inferior
2. pela largura da a´rvore
3. pela profundidade da a´rvore
Problema de minimizac¸a˜o
modelo
minimizar z =
n∑
j=1
cjxj
sujeito a`
n∑
j=1
aijxj ≥ bi ∀i = 1, . . . ,m
xj ∈ {0, 1} ∀j = 1, . . . , n.
caracter´ısticas
I ordenac¸a˜o no vetor c
c1 ≤ c2 ≤ . . . ≤ cn
I vetor c todo possitivo
se cj , fazer xj = (1− x ′j ), onde x ′j ∈ {0, 1}
Linear Inteira =⇒ Programac¸a˜o Linear Bina´ria
Todo problema de Programac¸a˜o Linear Inteira pode ser
transformado em Programac¸a˜o Linear Bina´ria. Por exemplo, se
0 ≤ x ≤ u, onde 2n−1 < u < 2n
enta˜o cada valor via´vel de x pode ser expresso como:
x =
n∑
i=0
2iyi , com yi ∈ {0, 1}
Assim a varia´vel x pode ser substituida em todo o problema por
esta soma envolvendo (n + 1) varia´veis bina´rias.
Algoritmo Branch-and-bound para PLIB - Balas [1]
Notac¸a˜o
I soluc¸a˜o parcial: subconjunto de soluc¸o˜es onde se conhece o
valor de k primeiras varia´veis do conjunto total das n varia´veis
do problema (x1, . . . , xk−1, xk , xk+1, . . . , xn);
I soluc¸a˜o completa: soluc¸a˜o onde se conhece o valor de todas
as n varia´veis do problema;
I conclusa˜o de uma soluc¸a˜o parcial: e´ uma soluc¸a˜o completa
partindo de uma soluc¸a˜o parcial
(x1, . . . , xk−1, xk , xk+1, . . . , xn);
I z∗k : valor o´timo da func¸a˜o objetivo quando a soluc¸a˜o onde a s
k primeiras varia´veis foram fixadas e as n − k varia´veis
restantes forem nulas (xj = 0 para j = k + 1, . . . , n) for
soluc¸a˜o via´vel do problema.
Algoritmo Branch-and-bound para PLIB - Balas [1]
Notac¸a˜o
I soluc¸a˜o parcial: subconjunto de soluc¸o˜es onde se conhece o
valor de k primeiras varia´veis do conjunto total das n varia´veis
do problema (x1, . . . , xk−1, xk , xk+1, . . . , xn);
I soluc¸a˜o completa: soluc¸a˜o onde se conhece o valor de todas
as n varia´veis do problema;
I conclusa˜o de uma soluc¸a˜o parcial: e´ uma soluc¸a˜o completa
partindo de uma soluc¸a˜o parcial
(x1, . . . , xk−1, xk , xk+1, . . . , xn);
I z∗k : valor o´timo da func¸a˜o objetivo quando a soluc¸a˜o onde a s
k primeiras varia´veis foram fixadas e as n − k varia´veis
restantes forem nulas (xj = 0 para j = k + 1, . . . , n) for
soluc¸a˜o via´vel do problema.
Algoritmo Branch-and-bound para PLIB - Balas [1]
Notac¸a˜o
I soluc¸a˜o parcial: subconjunto de soluc¸o˜es onde se conhece o
valor de k primeiras varia´veis do conjunto total das n varia´veis
do problema (x1, . . . , xk−1, xk , xk+1, . . . , xn);
I soluc¸a˜o completa: soluc¸a˜o onde se conhece o valor de todas
as n varia´veis do problema;
I conclusa˜o de uma soluc¸a˜o parcial: e´ uma soluc¸a˜o completa
partindo de uma soluc¸a˜o parcial
(x1, . . . , xk−1, xk , xk+1, . . . , xn);
I z∗k : valor o´timo da func¸a˜o objetivo quando a soluc¸a˜o onde a s
k primeiras varia´veis foram fixadas e as n − k varia´veis
restantes forem nulas (xj = 0 para j = k + 1, . . . , n) for
soluc¸a˜o via´vel do problema.
Algoritmo Branch-and-bound para PLIB - Balas [1]
Notac¸a˜o
I soluc¸a˜o parcial: subconjunto de soluc¸o˜es onde se conhece o
valor de k primeiras varia´veis do conjunto total das n varia´veis
do problema (x1, . . . , xk−1, xk , xk+1, . . . , xn);
I soluc¸a˜o completa: soluc¸a˜o onde se conhece o valor de todas
as n varia´veis do problema;
I conclusa˜o de uma soluc¸a˜o parcial: e´ uma soluc¸a˜o completa
partindo de uma soluc¸a˜o parcial
(x1, . . . , xk−1, xk , xk+1, . . . , xn);
I z∗k : valor o´timo da func¸a˜o objetivo quando a soluc¸a˜o onde a s
k primeiras varia´veis foram fixadas e as n − k varia´veis
restantes forem nulas (xj = 0 para j = k + 1, . . . , n) for
soluc¸a˜o via´vel do problema.
Construc¸a˜o da a´rvore de pesquisa
Caracter´ısticas da a´rvore de pesquisa
1. ve´rtice k: representa uma soluc¸a˜o parcial onde as k primeiras
varia´veis foram fixadas
2. branch: criar dois novos ve´rtices onde xk+1 = 0 e xk+1 = 1
3. limite iferior de cada ve´rtice e´ calculado:
LIk =

k∑
j=1
cjxj se xk = 1 (ou se k = 0 ou k = n);
k−1∑
j=1
cjxj + ck+1 se xk = 0.
Construc¸a˜o da a´rvore de pesquisa
Caracter´ısticas da a´rvore de pesquisa
1. ve´rtice k: representa uma soluc¸a˜o parcial onde as k primeiras
varia´veis foram fixadas
2. branch: criar dois novos ve´rtices onde xk+1 = 0 e xk+1 = 1
3. limite iferior de cada ve´rtice e´ calculado:
LIk =

k∑
j=1
cjxj se xk = 1 (ou se k = 0 ou k = n);
k−1∑
j=1
cjxj + ck+1 se xk = 0.
Construc¸a˜o da a´rvore de pesquisa
Caracter´ısticas da a´rvore de pesquisa
1. ve´rtice k: representa uma soluc¸a˜o parcial onde as k primeiras
varia´veis foram fixadas
2. branch: criar dois novos ve´rtices onde xk+1 = 0 e xk+1 = 1
3. limite iferior de cada ve´rtice e´ calculado:
LIk =

k∑
j=1
cjxj se xk = 1 (ou se k = 0 ou k = n);
k−1∑
j=1
cjxj + ck+1 se xk = 0.
Construc¸a˜o da a´rvore de pesquisa
outras caracter´ısticas
1. soluc¸a˜o via´vel no ve´rtice k: verificar se cada restric¸a˜o do
problema pode ser satisfeita. O ve´rtice k da a´rvore na˜o tem
soluc¸a˜o via´vel se
k∑
j=1
aij +
n∑
j=k+1
max{aij , 0} < bi
Exemplo
minimizar z = 3x1 + 5x2 + 6x3 + 9x4 + 10x5 + 10x6
sujeito a` −2x1 + 6x2 − 3x3 + 4x4 + x5 − 2x6 ≥ 2
−5x1 − 3x2 + x3 + 3x4 − 2x5 + x6 ≥ −2
5x1 − x2 + 4x3 − 2x4 + 2x5 − x6 ≥ 3
xj ∈ {0, 1} ∀j = 1, . . . , 6.
Definic¸a˜o
Modelo
minimizar z =
n∑
j=1
cjxj
sujeito a`
n∑
j=1
aijxj ≥ bi ∀i = 1, . . . , n
xj ∈ IN ∀j = 1, . . . , k(k < n),
xj ≥ 0 ∀j = k + 1, . . . , n.
Quando i = n, este problema e´ uma problema de Programac¸a˜o
Linear Inteira.
Algoritmo branch-and-bound para PLIM
Origem
Proposto por Dakin [2]baseado em Land e Doig [3].
Bibliografia
E. Balas.
An algorithm for solving linera programs with zero-one
variables.
Operations Research, 13(4):517–546, 1965.
R. J. Dakin.
A tree search algorithm for mixed integer programming
problems.
Computer Journal, 8(3):250–255, 1965.
A. H. Land and A. G. Doig.
An automatic method for solving discrete programming
problems.
Econometrica, 28:497–520, 1960.
	Programação Inteira
	Introdução
	Definição
	Técnica branch-and-baund
	Algoritmo branch-and-baund
	Programação Linear Binária
	Definição
	Algoritmo branch-and-bound para PLIB - Balas balas65
	Programação Linear Inteira Mista
	Definição
	Algoritmo branch-and-bound para PLIM
	Bibliografia

Outros materiais