Branch Bound

Relembrando aula passada...
 A programação inteira advém da necessidade de modelar decisões que tenham características discretas;

x2

∗
𝑥𝑅𝐿

 Definições:

c

 Quanto composto somente de variáveis inteiras  programação inteira (PI);
 Quando composto tanto por variáveis inteiras quanto variáveis contínuas 
Programação inteira mista (PIM);

 Apesar de parecer uma alteração simples, a consideração de variáveis de domínio inteiro geralmente torna o problema muito mais complexo em termos de resolução...

1.5 2

x1

x2

3 c 𝑥∗
1.5 2

x1

IND2504 - Métodos Quantitativos - 2014.2 - Prof. Fabrício Oliveira

Relembrando aula passada...
 Tipos clássicos de modelos que envolvem variáveis inteiras:





Problema de alocação de tarefas
Problema da mochila
Problema da cobertura
Problema do caixeiro viajante
Máquinas

c12

2

1

Tarefas

c61

c56

c23

5

3 c34 c45

4

6

2

1
S
1

5

1

3
3

2
4

6

S

S
3

2

IND2504 - Métodos Quantitativos - 2014.2 - Prof. Fabrício Oliveira

Relembrando aula passada...
 Truques de modelagem:
 Truque 1: Modelagem de custos fixos;
 Truque 2: Restrições disjuntivas;
 Truque 3: Economia de escala

IND2504 - Métodos Quantitativos - 2014.2 - Prof. Fabrício Oliveira

Solução de PI
 Dentre as formas conhecidas para a solução de problemas inteiros, a mais difundida é conhecida pelo nome de “Branch-and-Bound”
 “Branch” - Ramificar;
 “Bound” - Limitar;

 A ideia é que o problema principal pode ser sequencialmente subdividido (“branch”) até que o final de um ramo revele uma solução viável e, eventualmente, ótima.
 Vamos primeiro passar por alguns conceitos importantes...

IND2504 - Métodos Quantitativos - 2014.2 - Prof. Fabrício Oliveira

Solução de PI
 Da aula passada, vamos relembrar o conceito de relaxação linear:
 Seja o problema PPI:

𝑀𝑎𝑥.𝑥 𝑧 = 4𝑥1

−𝑥2

x2

𝑠. 𝑎: 7𝑥1 −2𝑥2