Appunti sul metodo del Branch And Bound

Appunti sul metodo

Branch and Bound

Simone Baldelli

Indice

Introduzione 2

Metodo del Branch and Bound applicato al problema dello zaino . . . . . 2

Metodo dello zaino (knapsack) . . . . . . . . . . . . . . . . . . . . . 2

Esempio di metodo Branch and Bound . . . . . . . . . . . . . . . . . 3

Riferimenti bibliograci 5

Elenco delle gure

1 Albero dei sottoproblemi . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Semplice esempio graco . . . . . . . . . . . . . . . . . . . . . . . . . 3

1

BRANCH AND BOUND 2

Introduzione

Abbiamo a disposizione un problema di PLI di minimo in forma standard:

min T

c x

Ax = b

≥

x 0

n

∈

x Z

Ingredienti del metodo

1. Ottimo corrente [La migliore soluzione ammissibile intera disponi-

∗ ∗

→

x z

CI

bile]

2. Generatore di sottoproblemi (Branch)

3. Risoluzione dei rilassamenti continui (Bound)

4. Chiusura dei sottoproblemi

è soluzione ottima del rilassamento continuo del problema iniziale.

x

Se non è intero non è intero. Genero due sottoproblemi:

⇒

x x i x ≥ bx c

≤ bx c x + 1

x

i i i i ...

...

...

... Albero dei sottoproblemi

Figura 1:

Esempio:



 3

2.4

 



 2 

 

 3.1

x =  



 5 



 

0

 

0

La seconda riga genera due sotto problemi e , calcolo l'ottimo del

≤ ≥

x 2 x 3

2 2

sottoproblema, se non è migliore dell'attuale chiudo il sottoproblema.

Metodo del Branch and Bound applicato al problema dello zaino

Metodo dello zaino (knapsack)

Sia dato uno zaino che possa sopportare un determinato peso. Siano dati inoltre

oggetti, ognuno dei quali caratterizzato da un peso e un valore. Il problema

N

si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere il

BRANCH AND BOUND 3

Problema dello zaino

Figura 2:

maggiore valore senza eccedere il peso sostenibile dallo zaino stesso.

Formalmente: min · · ·

c x + c x + + c x

1 1 2 2 n n

· · · ≤

a x + a x + + a x b

1 1 2 2 n n

∈ {0,

x 1}, i = 1, 2, . . . , n

Senza perdita di generalità possiamo scrivere c

c c

≥ ≥ · · · ≥

2 n

1

a a a

n

1 2

sono ordinate in ordine decrescente sul rapporto protto/ingombro. Il rilassamento

continuo è min · · ·

c x + c x + + c x

1 1 2 2 n n

· · · ≤

a x + a x + + a x b

1 1 2