Esercizio 1

Esercizio 1

Dato il seguente problema di Knapsack 0-1

max 30x

+ 36x

+ 15x

+ 11x

+ 5x

+ 3x

9x

+ 12x

+ 6x

+ 5x

+ 3x

+ 2x

< 17 x ∈ {0,1}

risolvere il problema tramite l’algoritmo di Branch-and-Bound.

Esercizio 1

Poiché in corrispondenza di ogni nodo dell’albero dovremo risolvere un problema di Knapsack continuo, riordiniamo gli oggetti in modo tale

che

p

a

≥ p

a

≥.. .≥ p

a

p₁/a₁ = 30/9 = 3,333 ⇒ y₁ p₂/a₂ = 36/12 = 3 ⇒ y₂ p₃/a₃ = 15/6 = 2,5 ⇒ y₃ p₄/a₄ = 11/5 = 2,2 ⇒ y₄ p₅/a₅ = 5/3 = 1,666 ⇒ y₅ p₆/a₆ = 3/2 = 1,5 ⇒ y₆

Gli oggetti sono già ordinati ⇒ Conserviamo la formulazione iniziale

Esercizio 1

Sia P₀ il rilassamento lineare associato al sottoproblema S₀ del nodo radice

max 30x₁ + 36x₂ + 15x₃ + 11x₄ + 5x₅ + 3x₆ 9x₁ + 12x₂ + 6x₃ + 5x₄ + 3x₅ + 2x₆ < 17 0 < x_i < 1, i = 1, …,6

Calcoliamo la soluzione associata all’upper bound utilizzando l’algoritmo per il Knapsack continuo:

x⁰_UB = [1, (17 – 9)/12, 0, 0, 0, 0] = [1, 2/3, 0, 0, 0, 0] ⇒ z⁰_UB = 54

Per il lower bound, consideriamo una soluzione ammissibile data da x⁰_LB = [1, 0, 0, 0, 0, 0] ⇒ z⁰_LB = 30 = z_LB.

S₀

z⁰_UB = 54

z⁰_LB = 30 = z_LB

Generiamo i due sottoproblemi S₁ t.c. x2 = 0

S₂ t.c. x2 = 1

S₁ S₂

x₂ = 1 x₂ = 0

Sia P₁ il rilassamento lineare associato al sottoproblema S₁ (x₂ = 0) max 30x₁ + 15x₃ + 11x₄ + 5x₅ + 3x₆

9x₁ + 6x₃ + 5x₄ + 3x₅ + 2x₆ < 17 0 < x_i < 1, i = 1, …,6

x¹_UB = [1, 0, 1, (17–15)/5, 0, 0] = [1, 0, 1, 2/5, 0, 0] ⇒ z¹_UB = 49,4 x¹_LB = [1, 0, 1, 0, 0, 0] = [1, 0, 1, 0, 0, 0] ⇒ z¹_LB = 45.

Poiché z¹_LB > z_LB, aggiorniamo il valore del lower bound corrente z_LB = 45

Esercizio 1

S₀

S₁ S₂

z¹_UB = 49.4 z¹_LB = 45

x₂ = 0 x₂ = 1

z_LB = 45

z⁰_UB = 54

z⁰_LB = 30 = z_LB

Sia P₂ il rilassamento lineare associato al sottoproblema S₂ (x₂ = 1)

max 30x₁ + 36 + 15x₃ + 11x₄ + 5x₅ + 3x₆

9x₁ + 12 + 6x₃ + 5x₄ + 3x₅ + 2x₆ < 17⇒ 9x₁ + 6x₃ + 5x₄ + 3x₅ + 2x₆ < 5 0 < x_i < 1, i = 1, …,6

x²_UB = [(17–12)/9, 1, 0, 0, 0, 0] = [5/9, 1, 0, 0, 0, 0] ⇒ z²_UB = 52,6 x²_LB = [0, 1, 0, 0, 0, 0] ⇒ z²_LB = 36.

z²_UB = 52.6 z²_LB = 36

Esercizio 1

S₀

S₁ S₂

z¹_UB = 49.4 z¹_LB = 45

x₂ = 0 x₂ = 1

z_LB = 45

z⁰_UB = 54

z⁰_LB = 30 = z_LB

z²_UB = 52.6 z²_LB = 36

Da S₂, generiamo i due sottoproblemi S₃ t.c. x₁ = 0

S₄ t.c. x₁ = 1

Sia P₃ il rilassamento lineare associato al sottoproblema S₃ (x₂ = 1, x₁=0) max 36 + 15x₃ + 11x₄ + 5x₅ + 3x₆

6x₃ + 5x₄ + 3x₅ + 2x₆ < 5 0 < x_i < 1, i = 1, …,6 x³_UB = [0, 1, 5/6, 0, 0, 0] ⇒ z³_UB = 48,5 x³_LB = [0, 1, 0, 0, 0, 0] ⇒ z³_LB = 36.

S₃ S₄

x₁ = 0 x₁ = 1

z³_UB = 48.5 z³_LB = 36

Esercizio 1

S₀

S₁ S₂

z¹_UB = 49.4 z¹_LB = 45

x₂ = 0 x₂ = 1

z⁰_UB = 54

z⁰_LB = 30 = z_LB

z²_UB = 52.6 z²_LB = 36

Da S₂, generiamo i due sottoproblemi S₃ t.c. x₁ = 0

S₄ t.c. x₁ = 1

Sia P₄ il rilassamento lineare associato al sottoproblema S₄ (x₂ = x₁=1) max 30 + 36 + 15x₃ + 11x₄ + 5x₅ + 3x₆

9 + 12 + 6x₃ + 5x₄ + 3x₅ + 2x₆ < 17 ⇒ 6x₃+5x₄+3x₅+2x₆ < 17– 21 0 < x_i < 1, i = 1, …,6

Poiché P₄ è inammissibile, il nodo S₄ può essere chiuso per inammissibilità.

S₃ S₄

x₁ = 0 x₁ = 1

z³_UB = 48.5 z³_LB = 36

Esercizio 1

×

inammissibilità

Esercizio 1

Da S₁, generiamo i due sottoproblemi S₅ t.c. x₄ = 0

S₆ t.c. x₄ = 1

S₀

S₁ S₂

z¹_UB = 49.4 z¹_LB = 45

x₂ = 0 x₂ = 1

z⁰_UB = 54

z⁰_LB = 30 = z_LB

z²_UB = 52.6 z²_LB = 36

S₃ S₄

x₁ = 0 x₁ = 1

z³_UB = 48.5

z³_LB = 36 inammissibilità

×

z_LB = 45

S₅ S₆

x₄ = 0 x₄ = 1

z⁵_UB = 48.33 z⁶_LB = 45

Sia P₅ il rilassamento lineare associato al sottoproblema S₁ (x₂ =x₄ = 0) max 30 x₁ + 15x₃ + 5x₅ + 3x₆

9x₁ + 6x₃ + 3x₅ + 2x₆ < 17 0 < x_i < 1, i = 1, …,6

x⁵_UB = [1, 0, 1, 0, (17–15)/3, 0] = [1, 0, 1, 0, 2/3, 0] ⇒ z⁵_UB = 48,33 x⁵_LB = [1, 0, 1, 0, 0, 0] ⇒ z⁵_LB = 45.

Esercizio 1

Da S₁, generiamo i due sottoproblemi S₅ t.c. x₄ = 0

S₆ t.c. x₄ = 1

S₀

S₁ S₂

z¹_UB = 49.4 z¹_LB = 45

x₂ = 0 x₂ = 1

z⁰_UB = 54

z⁰_LB = 30 = z_LB

z²_UB = 52.6 z²_LB = 36

S₃ S₄

x₁ = 0 x₁ = 1

z³_UB = 48.5

z³_LB = 36 inammissibilità

×

z_LB = 45

S₅ S₆

x₄ = 0 x₄ = 1

z⁵_UB = 48.33 z⁶_LB = 45

Sia P₆ il rilassamento lineare associato al sottoproblema S₆ (x₂ = 0, x₄=1) max 30 x₁ + 15x₃ + 11 + 5x₅ + 3x₆

9x₁ + 6x₃ + 5 + 3x₅ + 2x₆ < 17 ⇒ 9x₁ + 6x₃ + 3x₅ + 2x₆ < 12 0 < x_i < 1, i = 1, …,6

x⁶_UB = [1, 0, (12–9)/6 , 1, 0, 0] = [1, 0, 1/2, 1, 0, 0] ⇒ z⁶_UB = 48,5 x⁶_LB = [1, 0, 0, 1, 0, 0] ⇒ z⁶_LB = 41.

z⁶_UB = 48.5 z⁶_LB = 41

S₀

S₁ S₂

z¹_UB = 49.4 z¹_LB = 45

x₂ = 0 x₂ = 1

z_LB = 45

z⁰_UB = 54

z⁰_LB = 30 = z_LB

z²_UB = 52.6 z²_LB = 36

Da S₃, generiamo i due sottoproblemi S₇ t.c. x₅ = 0

S₈ t.c. x₅ = 1

S₅ S₆

x₄ = 0 x₄ = 1

z⁵_UB = 48.33 z⁵_LB = 45

z⁶_UB = 48.5

z⁶_LB = 41 S₃ S₄

x₁ = 0 x₁ = 1

z³_UB = 48.5

z³_LB = 36 inammissibilità

×

S₇ S₈

x₅ = 0 x₅ = 1 Sia P₇ il rilassamento lineare associato al sottoproblema S₇ (x₂=x₄=x₅=0)

max 30x₁ + 15x₃ + 3x₆ 9x₁ + 6x₃ + 2x₆ < 17 0 < x_i < 1, i = 1, …,6 x⁷_UB = [1, 0, 1, 0, 0, 1] ⇒ z⁷_UB = 48

x⁷_LB = [1, 0, 1, 0, 0, 1] ⇒ z⁷_LB = 48 ⇒ z_LB = 48.

S₇

z⁷_UB = 48 z⁷_LB = 48

×

z_LB = 48

OPT .

Esercizio 1

S₀

S₁ S₂

z¹_UB = 49.4 z¹_LB = 45

x₂ = 0 x₂ = 1

z_LB = 45

z⁰_UB = 54

z⁰_LB = 30 = z_LB

z²_UB = 52.6 z²_LB = 36

Da S₃, generiamo i due sottoproblemi S₇ t.c. x₅ = 0

S₈ t.c. x₅ = 1

S₅ S₆

x₄ = 0 x₄ = 1

z⁵_UB = 48.33 z⁵_LB = 45

z⁶_UB = 48.5

z⁶_LB = 41 S₃ S₄

x₁ = 0 x₁ = 1

z³_UB = 48.5

z³_LB = 36 inammissibilità

×

S₇ S₈

x₅ = 0 x₅ = 1 Sia P₈ il rilassamento lineare associato al sottoproblema S₈ (x₂=x₄=0, x₅=1)

max 30x₁ + 15x₃ + 5 + 3x₆

9x₁ + 6x₃ + 3 + 2x₆ < 17 ⇒ 9x₁+6x₃+2x₆ < 14 0 < x_i < 1, i = 1, …,6

x⁸_UB = [1, 0, (14–9)/6, 0, 1, 0]=[1,0,5/6,0,1,0] ⇒ z⁸_UB = 47,5 x⁸_LB = [1, 0, 0, 0, 1, 0] ⇒ z⁸_LB = 35

S₇

z⁷_UB = 48 z⁷_LB = 48

×

z_LB = 48

OPT

Poiché z⁸_UB = 47,5 < z_LB, il nodo S₈ può essere chiuso per bound.

z⁸_UB = 47.5 z⁸_LB = 35

bound.

×

Esercizio 1

Per lo stesso motivo, anche i nodi S₃ ed S₆ possono essere chiusi per bound.

×

bound. bound.

×

Per determinare il valore finale ottimo del problema, consideriamo tutti i nodi che sono stati chiusi per ottimalità e prendiamo la soluzione che da’ il massimo valore della funzione obiettivo.

Nel nostro caso il valore ottimo è dato da z*=48 e corrisponde alla soluzione x* = [1,0,1,0,0,1] associata al nodo S

.

Esercizio 1

S₀

S₁ S₂

z¹_UB = 49.4 z¹_LB = 45

x₂ = 0 x₂ = 1

z_LB = 45

z⁰_UB = 54

z⁰_LB = 30 = z_LB

z²_UB = 52.6 z²_LB = 36

S₅ S₆

x₄ = 0 x₄ = 1

z⁵_UB = 48.33 z⁵_LB = 45

z⁶_UB = 48.5

z⁶_LB = 41 S₃ S₄

x₁ = 0 x₁ = 1

z³_UB = 48.5

z³_LB = 36 inammissibilità

×

S₇ S₈

x₅ = 0 x₅ = 1

S₇

z⁷_UB = 48 z⁷_LB = 48

×

z_LB = 48

OPT

z⁸_UB = 47.5 z⁸_LB = 35

bound.

×

Esercizio 1

×

bound. bound.

×

Esercizio 2

Dato il seguente problema di Knapsack

max 6 x₁ + 10 x₂ + 12 x₃

x₁ + 2x₂ + 3 x₃ < 5 (KP) x ∈ {0,1}³

risolvere il problema tramite l’algoritmo di programmazione dinamica.

Esercizio 2

max 6 x

+ 10 x

+ 12 x

x

+ 2x

+ 3 x

< 5 (KP) x ∈ {0,1}

Calcoliamo la formula di ricorsione per r = 1:

z

(0) = 0 ⇒ x

= 0

z

(1) = 6 ⇒ x

= 1

z

(2) = 6 ⇒ x

= 1

z

(3) = 6 ⇒ x

= 1

z

(4) = 6 ⇒ x

= 1

z

(5) = 6 ⇒ x

= 1

d

r 0 1 2 3 4 5

1

(0,*,*)

0

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

2 z

(0) z

(1) z

(2) z

(3) z

(4) z

(5) 3 z

(0) z

(1) z

(2) z

(3) z

(4) z

(5)

Rappresentiamo questi valori in una tabella di dimensione n × b = 3 × 5, in cui ogni elemento contiene z

(d).

Il simbolo * nella soluzione indica che la variabile non è stata ancora fissata

Esercizio 2

Calcoliamo ora z

(d):

Per d = {0, 1}

z

(0) = z

(0) = 0 ⇒ x

= 0 z

(1) = z

(1) = 6 ⇒ x

= 0 Per d = {2, 3, 4, 5}

z

(2) = max {z

(2), z

(0) + c

} = max {6, 10} = 10 ⇒ x

= 1 z

(3) = max {z

(3), z

(1) + c

} = max {6, 16} = 16 ⇒ x

= 1 z

(4) = max {z

(4), z

(2) + c

} = max {6, 16} = 16 ⇒ x

= 1 z

(5) = max {z

(5), z

(3) + c

} = max {6, 16} = 16 ⇒ x

= 1 Riportando questi valori in tabella si ha:

Esercizio 2

d

r 0 1 2 3 4 5

1

(0,*,*)

0

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

2

(0,0,*)

0

(1,0,*)

6

(0,1,*)

10

(1,1,*)

16

(1,1,*)

16

(1,1,*)

16

3 z

(0) z

(1) z

(2) z

(3) z

(4) z

(5)

Esercizio 2

Calcoliamo ora z

(d):

Per d = {0, 1, 2}

z

(0) = z

(0) ⇒ x

= 0 z

(1) = z

(1) ⇒ x

= 0 z

(2) = z

(2) ⇒ x

= 0 Per d = {3, 4, 5}

z

(3) = max {z

(3), z

(0) + c

} = max {16, 12} = 16 ⇒ x

= 0 z

(4) = max {z

(4), z

(1) + c

} = max {16, 18} = 18 ⇒ x

= 1 z

(5) = max {z

(5), z

(2) + c

} = max {16, 22} = 22 ⇒ x

= 1 Riportando questi valori in tabella si ha:

Esercizio 2

d

r 0 1 2 3 4 5

1

(0,*,*)

0

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

2

(0,0,*)

0

(1,0,*)

6

(0,1,*)

10

(1,1,*)

16

(1,1,*)

16

(1,1,*)

16

3

(0,0,0)

0

(1,0,0)

6

(0,1,0)

10

(1,1,0)

16

(1,0,1)

18

(0,1,1)

22

Pertanto, la soluzione ottima è x

= (0, 1, 1) di valore 22.

Esercizio 2

Esercizio 3

Dato il seguente problema di Knapsack 0-1

max 22x₁ + 8x₂ – 12x₃ + 16x₄ 7x₁ + 3x₂ – 4x₃ + 5x₄ < 10

x ∈ {0,1}⁴

risolvere il problema tramite l’algoritmo di Branch-and-Bound.

Esercizio 3

Poiché la variabile x

ha coefficiente negativo, applichiamo il seguente cambio di variabile x'

= 1 – x

per ricondurci ad un problema di Knapsack 0-1 in cui i coefficienti del vincolo e della funzione obiettivo sono tutti non negativi.

Il problema diventa

– 12 + max 22x

+ 8x

+ x'

+ 16x

7x

+ 3x

+ 4x'

+ 5x

< 14

x ∈ {0,1}

Possiamo momentaneamente trascurare la costante –12 ricordandoci

di aggiungerla al valore finale della soluzione di branch & bound.

Esercizio 3

Riordiniamo ora gli oggetti in modo tale che

p

a

≥ p

a

≥.. .≥ p

a

p₁/a₁ = 22/7 = 3,14 ⇒ y₂ p₂/a₂ = 8/3 = 2,66 ⇒ y₄ p₃/a₃ = 12/4 = 3 ⇒ y₃ p₄/a₄ = 16/5 = 3,2 ⇒ y₁

Riscriviamo ora il problema nelle nuove variabili y_i

max 16y₁ + 22y₂ + 12y₃ + 8y₄ 5y₁ + 7y₂ + 4y₃ + 3y₄ < 14

y ∈ {0,1}⁴

Esercizio 3

Sia P₀ il rilassamento lineare associato al sottoproblema S₀ del nodo radice

max 16y₁ + 22y₂ + 12y₃ + 8y₄ 5y₁ + 7y₂ + 4y₃ + 3y₄ < 14 0 < y_i < 1, i = 1, …,4

Calcoliamo la soluzione associata all’upper bound utilizzando l’algoritmo per il Knapsack continuo:

y⁰_UB = [1, 1, 1/2, 0] ⇒ z⁰_UB = 44

Per il lower bound, consideriamo una soluzione ammissibile data da x⁰_LB = [1, 1, 0, 0] ⇒ z⁰_LB = 38 = z_LB.

S₀

z⁰_UB = 44

z⁰_LB = 38 = z_LB

Generiamo i due sottoproblemi S₁ t.c. y₃ = 0

S₂ t.c. y₃ = 1

S₁ S₂

y₃ = 1 y₃ = 0

Sia P₁ il rilassamento lineare associato al sottoproblema S₁ (y₃ = 0) max 16y₁ + 22y₂ + 8x₄

5y₁ + 7y₂ + 3y₄ < 14 0 < y_i < 1, i = 1, …,4 y¹_UB = [1, 1, 0, 2/3] ⇒ z¹_UB = 43,33 z¹_LB = [1, 1, 0, 0] ⇒ z¹_LB = 38.

Esercizio 3

S₀

S₁ S₂

z¹_UB = 43.33 z¹_LB = 38

y₃ = 0 y₃ = 1

z⁰_UB = 44

z⁰_LB = 38 = z_LB

Sia P₂ il rilassamento lineare associato al sottoproblema S₂ (y₃ = 1)

max 16y₁ + 22y₂ + 12 + 8y₄

5y₁ + 7y₂ + 3y₄ < 10 0 < y_i < 1, i = 1, …,4

y²_UB = [1, 5/7, 1, 0] ⇒ z²_UB = 43,7 y²_LB = [1, 0, 1, 0] ⇒ z²_LB = 28.

z²_UB = 43.7 z²_LB = 28

Esercizio 3

Da S₁, generiamo i due sottoproblemi S₃ t.c. y₄ = 0

S₄ t.c. y₄ = 1

S₃ S₄

Sia P₃ il rilassamento lineare associato al sottoproblema S₃ (y₃ = y₄ = 0) max 16y₁ + 22y₂

5y₁ + 7y₂ < 14

0 < y_i < 1, i = 1, …,4 y³_UB = [1, 1, 0, 0] ⇒ z³_UB = 38

x³_LB = [1, 1, 0, 0] ⇒ z³_LB = 38.

z³_UB = 38 z³_LB = 38

Esercizio 3

S₀

S₁ S₂

y₃ = 0 y₃ = 1

y₄ = 0 y₄ = 1

Chiudiamo il nodo per ottimalità.

×

OPT

z¹_UB = 43.33 z¹_LB = 38

z⁰_UB = 44

z⁰_LB = 38 = z_LB

z²_UB = 43.7 z²_LB = 28

Da S₁, generiamo i due sottoproblemi S₃ t.c. x₄ = 0

S₄ t.c. x₄ = 1

Sia P₄ il rilassamento lineare associato al sottoproblema S₄ (y₃ = 0, y₄=1) max 16y₁ + 22y₂ + 8

5y₁ + 7y₂ < 11

0 < y_i < 1, i = 1, …,5 y⁴_UB = [1, 6/7, 0, 1] ⇒ z⁴_UB = 42,8 y⁴_LB = [1, 0, 0, 1] ⇒ z⁴_LB = 24.

Esercizio 3

S₃ S₄

S₀

S₁ S₂

y₃ = 0 y₃ = 1

y₄ = 0 y₄ = 1

×

OPT

z³_UB = 38 z³_LB = 38

z¹_UB = 43.33 z¹_LB = 38

z⁰_UB = 44

z⁰_LB = 38 = z_LB

z²_UB = 43.7 z²_LB = 28

z⁴_UB = 42.8 z⁴_LB = 24

Da S₂, generiamo i due sottoproblemi S₅ t.c. y₂ = 0

S₆ t.c. y₂ = 1

Sia P₅ il rilassamento lineare associato al sottoproblema S₅ (y₃ = 1, y₂=0) max 16y₁ + 12 + 8y₄

5y₁ + 3y₄ < 10

0 < y_i < 1, i = 1, …,4 y⁵_UB = [1, 0, 1, 1] ⇒ z⁵_UB = 36

y⁵_LB = [1, 0, 1, 1] ⇒ z⁵_LB = 36.

Esercizio 3

Chiudiamo il nodo per ottimalità o per bound.

S₅ S₆

y₂ = 0 y₂ = 1

z⁵_UB = 36 z⁵_LB = 36

S₃ S₄

S₀

S₁ S₂

y₃ = 0 y₃ = 1

y₄ = 0 y₄ = 1

×

OPT

×

z³_UB = 38 z³_LB = 38

z¹_UB = 43.33 z¹_LB = 38

z⁰_UB = 44

z⁰_LB = 38 = z_LB

z²_UB = 43.7 z²_LB = 28

z⁴_UB = 42.8 z⁴_LB = 24

Da S₂, generiamo i due sottoproblemi S₅ t.c. x₁ = 0

S₆ t.c. x₁ = 1

Sia P₆ il rilassamento lineare associato al sottoproblema S₆ (y₃ = 0, y₂=1) max 16y₁ + 22 + 12 + 8y₄

5y₁+3y₄ < 3 0 < y_i < 1, i = 1, …,4

y⁶_UB = [3/5, 1, 1, 0] ⇒ z⁶_UB = 43,6 y⁶_LB = [0, 1, 1, 1] ⇒ z⁶_LB = 34.

Esercizio 3

S₅ S₆

y₂ = 0 y₂ = 1

z⁵_UB = 36 z⁵_LB = 36

S₃ S₄

S₀

S₁ S₂

y₃ = 0 y₃ = 1

y₄ = 0 y₄ = 1

×

OPT

×

z³_UB = 38 z³_LB = 38

z¹_UB = 43.33 z¹_LB = 38

z⁰_UB = 44

z⁰_LB = 38 = z_LB

z²_UB = 43.7 z²_LB = 28

z⁴_UB = 42.8 z⁴_LB = 24

z⁶_UB = 43,6 z⁵_LB = 34

OPT/Bound

Da S₄, generiamo i due sottoproblemi S₇ t.c. y₂ = 0

S₈ t.c. y₂ = 1

S₇ S₈

y₂ = 0 y₂ = 1

S₇

Esercizio 3

S₅ S₆

y₂ = 0 y₂ = 1

z⁵_UB = 36 z⁵_LB = 36

S₃ S₄

S₀

S₁ S₂

y₃ = 0 y₃ = 1

y₄ = 0 y₄ = 1

×

OPT

×

z³_UB = 38 z³_LB = 38

z¹_UB = 43.33 z¹_LB = 38

z⁰_UB = 44

z⁰_LB = 38 = z_LB

z²_UB = 43.7 z²_LB = 28

z⁴_UB = 42.8 z⁴_LB = 24

OPT/Bound

Sia P₇ il rilassamento lineare associato al sottoproblema S₇ (y₃=y₂=0,y₄=1) max 16y₁ + 8

5y₁ < 11

0 < y_i < 1, i = 1, …,4 y⁷_UB = [1, 0,0, 1] ⇒ z⁷_UB = 20

y⁷_LB = [1, 0, 0, 1] ⇒ z⁷_LB = 20

Poiché y⁷_UB è intera il nodo S₇ può essere chiuso per ottimalità.

Osserviamo che questo nodo potrebbe anche essere chiuso per bound in quanto z⁷_UB < z_LB.

Esercizio 3

Da S₄, generiamo i due sottoproblemi S₇ t.c. y₂ = 0

S₈ t.c. y₂ = 1

S₇ S₈

y₂ = 0 y₂ = 1

S₇

Esercizio 3

S₅ S₆

y₂ = 0 y₂ = 1

z⁵_UB = 36 z⁵_LB = 36

S₃ S₄

S₀

S₁ S₂

y₃ = 0 y₃ = 1

y₄ = 0 y₄ = 1

×

OPT

×

z³_UB = 38 z³_LB = 38

z¹_UB = 43.33 z¹_LB = 38

z⁰_UB = 44

z⁰_LB = 38 = z_LB

z²_UB = 43.7 z²_LB = 28

z⁴_UB = 42.8 z⁴_LB = 24

×

OPT/Bound

OPT/Bound

z⁷_UB = 20 z⁷_LB = 20

Sia P

il rilassamento lineare associato al sottoproblema S

(y

=0,y

=y

=1)

max 16y

+ 30 5y

< 4

0 < y

< 1, i = 1, …,4

y

= [4/5, 1,0, 1] ⇒ z

= 42,8 y

= [0, 0, 1, 1] ⇒ z

= 30

Esercizio 3