Appunti sul metodo del Branch And Bound

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 2 n n

≤ ≤

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

che si risolve ponendo p tale che

∗ · · ·

x = 1, i = 1, . . . , p a + a + + a + a > b

1 2 p p+1

i

− · · ·

b (a + a + + a ) .

ottenendo così 1 2 p

∗

x =

p+1 a

p+1

Esempio: max 6x + 3x + 4x + 2x + x

1 2 3 4 5

≤

2x + x + 2x + x + x 4

1 2 3 4 5

∈ {0,

x , x , x , x 1}

1 2 3 4

Calcolo l'ottimo corrente:

 

1

0

  AMMISSIBILE Ottimo corrente: ∗

  ⇒

0 z = 6

x̄ =   c

 

0

 

0

- Risolvo il rilassamento continuo:

 

1

1

 

∗ 1

 

x =  

c 2

 

0

 

0

BRANCH AND BOUND 4

- Genero due sottoproblemi: P P

ponendo un vincolo aggiuntivo 1 2

x = 0 x = 1

3 3

- Risolvo il rilassamento continuo di :

P 1



 1

1 

 Aggiorno chiudo il sottoproblema

(1)

(1) ∗ ∗ ∗



 ⇒ ⇒

0 z = 11 > z x

x = , z P

c

c 1



 c c

CI



 1 

 0

perché le soluzioni sono intere e il massimo e migliore di quello ottenuto no ad ora.

- Risolvo il rilassamento continuo di :

P 2

→ ≤

x = 1 2x + x + x + x 2

3 1 2 4 5



 1

0 

 Chiudo perché le soluzioni sono intere ma il

(2) (2) ∗



 ⇒

1

x = z = 10 < z P

c c 2



 c



 0 

 0

massimo è minore del miglior risultato ottenuto no ad ora