5.1 Metodo Branch and Bound -...
Transcript of 5.1 Metodo Branch and Bound -...
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 1
5.1 Metodo Branch and Bound
Idea: Ricondurre la risoluzione di un problema difficile a
quella di sottoproblemi più semplici effettuando una
partizione (ricorsiva) della regione ammissibile.
Consideriamo un generico problema di ottimizzazione
min{ c(x) : x X }
Applicabile ai problemi di ottimizzazione combinatoria
e continua.
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 2
z = min{ c(x) : x X }
Operazione di “branching”:
Sia X = X1 … Xk una partizione di X in k sottoinsiemi
( Xi Xj = per ogni coppia i j )
e zi = min{ c(x) : x Xi } per i =1,…, k
Chiaramente z = min{ c(x) : x X } = min{z1,…, zk}
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 3
Operazione di “bounding”:
Per i-esimo sottoproblema sia zi = min{ c(x) : x Xi }
i) determinare una soluzione ottima di min{ c(x) : x Xi }
(modo esplicito), oppure
ii) dimostrare che Xi = (modo esplicito), oppure
iii) dimostrare che zi ≥ z’ = valore della migliore soluzione
ammissibile trovata finora (modo implicito).
Se un sottoproblema non è “risolto” vengono
generati nuovi sottoproblemi mediante “branching”.
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 4
“Branching”:
Suddividere la regione ammissibile X in sottoregioni esaustive ed esclusive (partizione).
Sia un generico PLI min{ cTx : Ax = b, x ≥ 0 interi }
5.1.1 Branch and Bound per PLI
Risolvere il rilassamento continuo
min{ cTx : Ax = b, x ≥ 0 }
e siano x una soluzione ottima e zPL = cTx il valore ottimo.
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 5
“Bounding”:
Determinare un “bound” (per difetto se PLI di min) sul
valore ottimo zi di un sottoproblema di PLI risolvendo il
relativo rilassamento continuo.
Se x intera, x è anche ottima per PLI, altrimenti
xh frazionaria e si considerano i due sottoproblemi:
PLI1: min{ cTx : Ax = b, xh ≤ ⌊xh⌋, x ≥ 0 interi }
PLI2: min{ cTx : Ax = b, xh ≥ ⌊xh⌋+1, x ≥ 0 interi }
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 6
6 5 4 3 2 1
x1
9
8
7
6
5
4
3
2
1
x2
z = 20
x = zPL = 41.25
15/4 9/4
max z = 8x1 + 5x2
x1 + x2 ≤ 6
9x1 + 5x2 ≤ 45
x1, x2 ≥ 0 interi
PLI
Esempio:
zPL ≥ z*PLI
9x1 + 5x2 = 45
x1 + x2 = 6
Poiché x1 e x2 frazionarie, sceglierne una per il passo di branching
ad esempio x1
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 7
Regione ammissibile X suddivisa in X1 e X2 imponendo:
x1 ≤ ⌊x1⌋ = 3 o x1 ≥ ⌊x1⌋+1 = 4 vincoli esaustivi
ed esclusivi
6 5 4 3 2 1
x1
9
8
7
6
5
4
3
2
1
x2
z = 20
Sottoproblema S1 sottoregione X1 Sottoproblema S2
sottoregione X2
sol. x = con zPL2 = 41
4 9/5
sol. x = con zPL1 = 39
3 3
intera! ⇒ z*PLI1 ≥ zPL1
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 8
Dopo aver considerato X1, migliore soluzione ammissibile
(intera) trovata finora:
x = con z = 39 3 3
Visto che zPL2 = 41 > 39, X2 può contenere una soluzione
ammissibile del PLI migliore.
⇒ Partizione di X2 in X3 e X4 imponendo:
x2 ≤ ⌊x2⌋=1 o x2 ≥ ⌊x2⌋+1=2
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 9
z = 20
x2 = 2
x2 = 1 1
2
3
4
x2
1 2 3 4 5 6 x1
Sottoproblema S3
sottoregione X3
Sottoproblema S4 è inammissibile (X4 = ø)
sol. x = con zPL3 = 365/9
40/9 1
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 10
Albero di branching:
PL
S1 S2
S3 S4
x1 ≥ 4 x1 ≤ 3
x2 ≤ 1 x2 ≥ 2
zPL2 = 41.25
zPL3 = 365/9 inammissibile
X4 = ø
zPL1 = 39
sol. intera
migliore sol.
ammissibile
trovata finora
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 11
Visto che zPL3 = 365/9 > 39, X3 può contenere una soluzione
ammissibile del PLI migliore.
⇒ Partizione di X3 in X5 e X6 imponendo:
x1 ≤ ⌊x1⌋ = 4 o x1 ≥ ⌊x1⌋+1 = 5
40/9 1 x =
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 12
z = 20
Sottoproblema S5
sol. di S5 : x = intera con zPL5 = 37 4 1
1
2
3
4
x2
1 2 3 4 5 6 x1
x1 = 4 x1 = 5 unica sol. ammissibile di S6
5 0
x = intera con zPL6 = 40
Soluzione intera (anche ammissibile per PLI) ma con valore peggiore di
x = con zPL1 = 39 3 3
Migliore soluzione trovata ⇒ soluzione ottima
Branch & Bound garantisce soluzione ottima (metodo esatto)
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 13
Albero di branching
49
415
4165
2
1
x
x
z
PL
PL
3
3
39
2
1
1
1
x
x
z
S
PL
59
4
41
2
1
2
2
x
x
z
S
PL
1
940
9365
2
1
3
3
x
x
z
S
PL
S4
X4 = ø
1
4
37
2
1
5
5
x
x
z
S
PL
0
5
40
2
1
6
6
x
x
z
S
PL
radice
intera intera
inammissibile
x1 ≤ 3
x2 ≤ 1
x1 ≤ 4
x1 ≥ 4
x2 ≥ 2
x1 ≥ 5
sol. intera
ottima
z*PLI = 40
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 14
L’albero non contiene necessariamente tutti i nodi possibili
(2d # foglie)
intera
Un nodo non ha figli -- è chiuso -- se
• vincoli iniziali + quelli sugli archi dalla radice sono
incompatibili (S4)
• soluzione del rilassamento continuo è intera (S1)
• soluzione ottima xPL del rilassamento continuo ha un
valore cTxPL peggiore di quello della migliore soluzione
ammissibile del PLI trovata finora.
≡ criterio di “bounding”
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 15
NB: Nel terzo caso la sottoregione ammissibile del
sottoproblema associato a quel nodo non può contenere
una soluzione intera migliore della migliore soluzione
del PLI trovata finora!
Criterio di “bounding” permette spesso di “eliminare” gran
parte dei sottoproblemi (chiudere i rispettivi nodi).
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 16
Scelta del nodo (sottoproblema) da elaborare:
• Prima nodi più profondi (tecnica “depth first”)
procedimento ricorsivo semplice ma costoso in
caso di scelta sbagliata
• Prima nodi più promettenti (“best bound first”)
con valore del rilassamento continuo migliore
Si generano tipicamente meno nodi ma problemi poco vincolati ⇒ si aggiorna raramente la
migliore soluzione ammissibile corrente
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 17
Scelta variabile (frazionaria) di branching
Non è detto che convenga scegliere la variabile xh con
parte frazionaria più vicina a 0,5 (sperando che il nuovo
vincolo sia più significativo per i due sottoproblemi.)
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 18
Struttura dati Branch & Bound: problema di min
• m = ultimo nodo
• xopt = migliore soluzione intera trovata finora
• zopt = cTxopt = costo migliore soluzione intera trovata finora
• Q = coda dei nodi foglia attivi (quelli che possono avere
nodi figli)
• Padre[t] = ±p p = indice nodo padre di t
+/- figlio di sinistra o di destra
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 19
• LB[t] = “lower bound” associato a t
• Vbranch[t] = indice h della variabile xh di branching
• Valore[t] = valore x*h della variabile di branching
NB: Se PL inammissibile, x* fittizio e cTx* = +∞
Se c intero, LB[m] = ⌈cTx*⌉
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 20
BEGIN
m:=1; Padre[1]:=0; Q:= ;
zopt:= valore soluzione euristica (eventualmente +∞);
risolvi il rilassamento continuo min{cTx : Ax = b, x ≥ 0} e sia
x* la soluzione ottima trovata;
LB[1]:= cTx*;
IF (x* intera) AND (cTx* < zopt) THEN
xopt:= x*; zopt:= c
Tx*
END-IF
IF LB[1] < zopt THEN
scegli la variabile frazionaria x*h di branching;
Vbranch[1]:= h; Valore[1]:= x*h;
Q := {1}
END-IF
WHILE Q ≠ 0 DO /* elabora i nodi figli attivi */
scegli un nodo t Q; poni Q:= Q \ {t};
h:= Vbranch[t]; val:= Valore[t];
...
Algoritmo Branch & Bound E
lab
ora
zione
rad
ice
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 21
FOR figlio:= 1 TO 2 DO /*genera i figli del nodo t */
m:= m+1;
IF figlio = 1 THEN Padre[m]:= t;
ELSE Padre[m]:= -t; END-IF
definisci il problema PLm associato al nodo m
(vincoli di PLt più xh ≤ ⌊val⌋ se figlio = 1,
o xh ≥ ⌈val⌉ se figlio = 2);
risolvi il problema PLm e sia x* la soluzione ottima trovata;
LB[m]:= cTx*;
IF (x* intera) AND (cTx* < zopt) THEN
xopt:= x*; zopt:= c
Tx*; /* aggiorna la soluzione ottima */
Q:= Q \ {jQ : LB[j] ≥ zopt};
END-IF
IF LB[m] < zopt THEN
scegli la variabile frazionari x*k di branching;
Vbranch[m]:= k; Valore[m]:= x*k;
Q:= Q {m};
END-IF
END-FOR
END-WHILE
END
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 22
Come aggiornare in modo efficiente il tableau ottimo del
rilassamento continuo corrente quando si aggiunge un solo
vincolo?
Si può utilizzare una variante del metodo del simplesso nota
come metodo del simplesso duale (basta un’unica iterazione!).
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 23
Branch & Bound applicabile anche a PLI misti:
considerare solo per “branching” le variabili frazionarie con
vincolo di interezza.
In realtà metodo generale per problemi di ottimizzazione discreta
Esempi: sequenziamento, commesso viaggiatore,…
# finito (ma elevatissimo) di sol. ammissibili
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 24
Basta
• Tecnica per suddividere un insieme di soluzioni ammissibili
in sottoinsiemi mutualmente esclusivi ed esaustivi (“branch”)
• Procedura per determinare un limite (inferiore se problema di
min) sul costo di qualsiasi soluzione ammissibile in un dato
sottoinsieme (“bound”)
NB: Branch-and-Bound (B & B) anche utilizzabile come
metodo approssimato (imponendo un limite su tempo
o nodi esplorati)
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 25
5.1.2 B & B per problemi di ottimizzazione combinatoria
Esempio: Problema di sequenziamento ( NP-difficile )
n lavori (jobs) da eseguire su una macchina
n = 4 jobs
tempo di
lavorazione scadenza
1 6 8
2 4 4
3 5 12
4 8 16
fine giorno 8
Tempi di lavorazioni e le date limite di consegna: in giorni
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 26
Per sequenza 1 – 2 – 3 – 4, ritardo totale = 0 + 6 + 3 + 7 = 16
definiamo xij =
Idea: suddividere l’insieme di tutte le soluzioni ammissibili
a seconda del job eseguito per ultimo.
Chiaramente x14 = 1 o x24 = 1 o x34 = 1 o x44 = 1
1 se job i è il j-esimo eseguito
0 altrimenti giorni
Determinare una sequenza che minimizza il ritardo totale.
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 27
D = ritardo totale
se x44 = 1, job 4 è completato alla
fine del giorno 6 + 4 + 5 + 8 = 23
cioè con ritardo di 23 – 16 = 7
1 D ≥ 15
2 D ≥ 19
3 D ≥ 11
4 D ≥ 7
5 D ≥ 14
6 D ≥ 18
7 D ≥ 10
8 D = 12
9 D = 16
x14 = 1 x24 = 1
x44 = 1
x34 = 1
x13 = 1
x23 = 1
x33 = 1
x12 = 1 x22 = 1
⋮
“Branching” effettuato sul nodo con
limite inferiore su D più piccolo.
nodo 4; nodo 7; nodo 8;…
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 28
Per nodo 7: job 4 per ultimo con ritardo di 7
job 3 per penultimo con ritardo di
6 + 4 + 5 – 12 = 3 giorni
15
⇒ D ≥ 7 + 3 = 10
nodo 8 (sequenza 2 – 1 – 3 – 4) sol. ammissibile candidata
con ritardo totale = 12.
NB: nodi 1, 2, 5 e 6 possono essere “chiusi”!
E. Amaldi – Fondamenti di R. O. – Politecnico di Milano 29
1 D ≥ 15
2 D ≥ 19
3 D ≥ 11
4 D ≥ 7
10 D ≥ 21
11 D ≥ 25
12 D ≥ 13
x14 = 1 x24 = 1
x44 = 1
x34 = 1
x13 = 1
x23 = 1
x43 = 1
⋮
11 + (6 + 4 + 8 – 16) = 13 11 + (6 + 4 + 8 – 8) = 21
job 1 penultimo
⇒ sequenza ottima: 2 – 1 – 3 – 4 con D =12
job 3 ultimo
job 4 penultimo