Reti Massimo Flusso Massimo Flusso Massimo Flusso

Massimo Flusso
Problema del Massimo Flusso MaxFlow(G(V,E),l,u,s,t,max):
Istanza: una rete G(V,E) caratterizzata da capacità minime l e massime u
sugli archi e su di essa un solo nodo sorgente s e un solo nodo pozzo t.
Soluzione: un flusso x da s a t che rispetti le capacità l e u.
Obiettivo: massimo flusso x.
Reti
Flussi, Alberi e Matroidi
versione 07/02/2006 12.45
Raffaele Pesenti
Raffaele Pesenti
2
Massimo Flusso
Massimo Flusso
[1,3]
Riduzione:
MaxFlow (G(V,E),l,u,s,t,max) ∝ MinCostFlow (G’(V’,E’), b’,c’,l’,u’,min)
•
•
•
•
•
•
•
[0,6]
V’← V
E’← E∪{(t,s)}
b’ = 0
c’ij=0 ∀(i,j)≠(t,s), c’ts=-1
l’ij ← lij ∀(i,j)≠(t,s), l’ts =0
u’ij ← uij ∀(i,j)≠(t,s), u’ts =∞
Il flusso su (t,s) in G’ corrisponde al massimo flusso tra s e t in G
G(V,E)
[-1,3]
[0,2]
[0,4]
[-2,5]
[1,3]
[0,6]
G’(V’,E’)
s
t
[0,3]
[0,5]
Commenti:
• Il costo cts=-1 rende conveniente il flusso su (s,t) in MinCostFlow
• Il problema MaxFlow è in P
Raffaele Pesenti
s
[0,9]
[0,6]
[0,9]
[0,6]
[-1,3]
t
[0,3]
[0,2]
[0,5]
[-2,5]
[0,4]
[0,∞]
3
Raffaele Pesenti
4
Massimo Flusso
Formulazione PL
Commenti:
• in seguito si considereranno solo archi (i,j) con capacità minima nulla l(i,j) =0
e con capacità massima non negativa u(i,j) ≥ 0.
• l’ipotesi precedente non è riduttiva se la capacità inferiore è negativa in
quanto, e.g.,
notazione
semplificata
[0,5]
5
[-2,5]
i
j
i
j
i
j
[0,2]
2
max f(t,s)
Σ(s,k) xsk - Σ(i,s) xis = f(t,s)
Σ(j,k) xjk - Σ(i,j) xij =0
∀ j∈V-{s,t}
Σ(t,k) xtk - Σ(i,t) xit = -f(t,s)
0 ≤ xij ≤ uij
∀ (i,j)∈ E-{(t,s)}
dove xij è il flusso per l’arco (i,j) e f(t,s) è il flusso tra s e t, interpretato come
flusso sull’arco di ritorno (t,s)
• nel caso di capacità inferiori positive si rimanda a lucidi successivi
Raffaele Pesenti
Il problema MaxFlow (G(V,E),l,u,s,t,max) può quindi essere formulato come
5
Raffaele Pesenti
6
Formulazione PL
Formulazione PL
Esempio:
Al problema MaxFlow (G(V,E),l,u,s,t,max) in figura
corrisponde:
max f(t,s)
πs:
π 1:
π 2:
πt:
λ(s,1):
λ(s,2):
λ(1,2):
λ(1,t):
λ(2,t):
Raffaele Pesenti
+ x(s,1) + x(s,2) = f(t,s)
−x(s,1) + x(1,2) + x(1,t) = 0
−x(s,2) - x(1,2) + x(2,t) = 0
−x(1,t) - x(2,t) =- f(t,s)
x(s,1) ≤ 2
x(s,2) ≤ 4
x(1,2) ≤ 3
x(1,t) ≤ 1
x(2,t) ≤ 5
x(i,j) ≥ 0 ∀ (i,j)
Commenti:
Il problema MaxFlow è risolvibile polinomilamente attraverso la
programmazione lineare.
Vale la pena di cercare se esistono caratteristiche specifiche del problema o
della sua soluzione che permettano lo sviluppo di algoritmi ad hoc di
risoluzione, più efficienti di quelli (general purpose) per la programmazione
lineare.
Ad esempio per quanto riguarda i problemi di SPP l’algoritmo di Dijkstra
sfrutta la proprietà che un percorso ottimo da s a t deve essere anche un
percorso ottimo da s a tutti i nodi intermedi.
Nell’ottica precedente si studiano i tagli e le reti residuali.
capacità
2
4
s
5
t
3
2
1
1
7
Raffaele Pesenti
8
Tagli s-t
Tagli s-t
Taglio s-t:
Dato una rete G(V,E) un taglio s-t è una partizione dei nodi V in due sottoinsiemi
(S,V- S) t.c. s∈S, t∈V-S.
Ad ogni taglio (S,V- S) sono associabili i seguenti sottoinsiemi di archi
CF={(i,j): (i,j)∈E, i∈S, j∈V-S}
CB={(i,j): (i,j)∈E, j∈S, i∈V-S}
C= CF ∪ CB
Anche C è spesso indicato come taglio.
S
s
C
arco forward
V-S
arco backward
t
Raffaele Pesenti
Flusso attraverso il taglio s-t:
Detto v il flusso che attraversa il taglio s-t esso è non superiore alla somma
u(S,V-S) delle capacità degli archi forward
v(S,V-S) =Σ(i,j)∈CF xij - Σ(p,q) ∈CB xpq≤ Σ(i,j)∈CF xij ≤ Σ(i,j)∈CF uij= u(S,V-S)
u(S,V-S) è detto capacità del taglio
Teorema debole del Max-Flow Min-Cut:
Il flusso massimo da s a t è non superiore alla capacità del taglio minimo
(i.e., minima capacità del taglio)
max f(t,s) ≤ minS u(S,V-S)
Dimostrazione:
sommare i vincoli di bilancio dei flussi per i nodi in S per ottenere il flusso del taglio
(S, V-S)
f(t,s) =Σ(i,j)∈CF xij - Σ(p,q) ∈CB xpq=v(S,V-S) ≤ Σ(i,j)∈CF xij ≤ Σ(i,j)∈CF uij= u(S,V-S)
9
Raffaele Pesenti
Tagli s-t
Rete residuale
Rete residuale:
Dato un problema MaxFlow (G(V,E),l,u,s,t,max) e un flusso ammissibile x, si
definisce rete residuale la rete Gx(V’,E’) delle capacità residue (ancora utilizzabili)
una volta imposto il flusso x.
In Gx(V’,E’)
– V’ = V
– E’={(i,j): (i,j)∈ E or (j,i)∈ E}
– l’=0
– u’ij = uij - xij se (i,j)∈ E,
– u’ij = xij se (j,i)∈ E
Esempio:
Dato il seguente problema MaxFlow (G(V,E),l,u,s,t,max)
taglio
2
+ x(s,1) + x(s,2)
= f(t,s)
−x(s,2) - x(1,2) +x(2,t) = 0
_________________________
+ x(s,1)
- x(1,2) + x(2,t) = f(t,s)
⇓
10
4
5
s
t
3
2
1
1
f(t,s) ≤ x(s,1) + x(2,t) ≤ 2+5 = 7
Proprietà:
• Se le capacità iniziali e il flusso sono interi anche le capacità residuali sono intere.
Raffaele Pesenti
11
Raffaele Pesenti
12
Rete residuale
flusso
Esempio:
Dato il problema MaxFlow (G(V,E),l,u,s,t,max)
e il flusso nella figura di destra, la
corrispondente rete residuale risulta essere come
in figura sottostante
2
3
1
s
(1) 2 5
4
s
capacità
(3)
3 (2)
2
(2)
1
1
Proprietà:
Se P(s,t) esiste e detto δ =min{u’ij: (i,j)∈P(s,t)} ( i.e., δ è la capacità minima
di un arco nel percorso) è possibile modificare il flusso originario x in modo
che il flusso complessivo f(s,t) da s a t aumenti di δ.
Infatti basta porre
– xij← xij + δ
se (i,j)∈P(s,t), (i,j)∈E (archi in P ed E concordi)
– xij← xij - δ
se (i,j)∈P(s,t), (j,i)∈E (archi in P ed E discordi)
– xij← xij
se (i,j)∉P(s,t)
3
1
Percorso aumentante:
Dato un problema MaxFlow (G(V,E),l,u,s,t,max) e un flusso ammissibile x, si
definisce percorso aumentante P(s,t) un qualunque percorso da s a t lungo
archi di capacità non nulla di Gx(V’,E’).
t
2
t
2 1
2
Percorso aumentante
1
Raffaele Pesenti
13
Raffaele Pesenti
Percorso aumentante
flusso
Esempio:
Dato il problema MaxFlow (G(V,E),l,u,s,t,max)
e il flusso nella figura di destra, un possibile
percorso aumentante con δ=1 è rappresentato
nella figura sottostante
2
3
1
s
2
2
2 1
1
2
1
Raffaele Pesenti
percorso aumentante
5
4
3 (2)
(2)
nuovo flusso
capacità
(3)
(2)
1
1
2
s
(3)
3 (1)
2
(2)
Dimostrazione:
(necessità) Ovvia.
(sufficienza) Sia S l’insieme dei nodi raggiungibili con un percorso da s sulla rete
residuale e V-S l’insieme dei rimanenti nodi. Per definizione di S e V-S non esiste
sulla rete residuale un arco (i,j) con capacità non nulla t.c. i∈ S e j∈ S-V, quindi
qualunque arco nella rete originale (i,j)∈ E t.c. i∈ S e j∈ S-V deve essere attraversato
da un flusso xij=uij, viceversa se (i,j)∈ E t.c. j∈ S e i∈ S-V deve essere attraversato da
un flusso xij=0. Il flusso che attraversa il taglio (S,V-S) coincide con la capacità del
taglio e quindi è ottimo per il teorema debole del Max-Flow Min-Cut.
5
4
t
(1)
1
Teorema del percorso aumentante:
Condizione necessaria e sufficiente di ottimalità di un flusso x è che non
esista alcun percorso aumentante sulla corrispondente rete residuale.
t
2
3
t
Percorso aumentante
(1)
s
14
1
15
Raffaele Pesenti
16
Algoritmo del cammino aumentante
Max-Flow Min-Cut
Teorema (forte) del Max-Flow Min-Cut:
Il flusso massimo da s a t è uguale alla capacità del taglio minimo
max f(t,s) = minS u(S,V-S)
(in presenza di lower bound il teorema diventa
max f(t,s) = minS (u(S,V-S)- l(V-S,S))
dove l(S,V-S) è definito in modo del tutto analogo a u(S,V-S))
Dimostrazione:
max f(t,s) ≤ minS u(S,V-S) in quanto già dimostrato, inoltre al flusso x che definisce max f(t,s)
deve essere associata una rete residuale in cui non esiste un percorso da s-t allora, quindi
x deve, per il teorema precedente, saturare le capacità di un taglio.
Raffaele Pesenti
17
Algoritmo del cammino aumentante AugmentingPath(G(V,E),l,u,s,t)
1. Inizializzazione.
x = 0; // flusso iniziale ammissibile nullo, si suppone l=0
2. Iterazione.
while Gx(V’,E’) contiene cammino aumentante P(s,t) {
δ =min{u’ij: (i,j)∈P(s,t)}
xij= xij + δ
se (i,j)∈P(s,t), (i,j)∈E
xij= xij - δ
se (i,j)∈P(s,t), (j,i)∈E
xij= xij
se (i,j)∉P(s,t)
}
Raffaele Pesenti
Generalizzazioni massimo flusso
Algoritmo del cammino aumentante
Commenti:
• L’algoritmo ha un approccio primale, parte da una soluzione ammissibile che
migliora progressivamente e termina trovando il flusso ottimo (vedi teoremi
precedenti)
• L’algoritmo funziona anche nel caso di lower bound positivi, solo che nella
fase inizializzazione deve essere determinato un primo flusso ammissibile e
le capacità residuali devono essere definite tenendo conto di lower bound
u’ij = uij - xij se (i,j)∈ E, u’ij = xij - lij se (j,i)∈ E
• L’algoritmo nella sua versione generale non è polinomiale, poiché nel caso
peggiore aumenta il flusso di un’unità ad ogni iterazione, quindi compie un
numero di iterazioni pari alla capacità del taglio minimo, quindi la sua
complessità è lineare in un parametro del problema invece che essere
logaritmica
• Scegliendo i percorsi aumentanti in modo opportuno si possono avere
algoritmi polinomiali. In particolare scegliendo sempre il percorso di
lunghezza (in numero di archi) minima sulla rete si può sviluppare un
algoritmo O(n2m)
Raffaele Pesenti
18
Sorgenti e pozzi multipli:
Il problema con sorgenti e pozzi multipli si riduce al problema con singola
sorgente e singolo pozzo
Esempio:
Il problema in figura (le capacità sono
omesse per brevità) con due sorgenti
s1, s2 e due pozzi t1, t2 diventa …
… problema di MaxFlow in figura
con una sorgente s e un pozzo t e
4 archi aggiuntivi di capacità infinita
∞
s
s1
t1
s2
t2
s1
t1
t
∞
s2
19
Raffaele Pesenti
∞
t2
∞
20
Generalizzazioni massimo flusso
Generalizzazioni massimo flusso
Determinazione di un flusso ammissibile:
Determinare un flusso ammissibile per un problema di
MinCostFlow (G (V,E), b,c,l,u,min) è riducibile ad un problema di MaxFlow
Esempio:
Il problema in figura con due sorgenti
b1, b2 e due pozzi b3, b4 diventa …
b1
… problema di MaxFlow in figura
con una sorgente s e un pozzo t e
b2
4 archi aggiuntivi di b1, b2, -b3, -b4,
le sorgenti e i pozzi originari perdono le
b1
loro caratteristiche. Il flusso ottenuto è
ammissibile se satura gli archi aggiunti,
s
altrimenti non esiste soluzione ammissibile b
2
per MinCostFlow
Raffaele Pesenti
Commenti:
• L’esempio di determinazione di un flusso ammissibile evidenzia che
condizione necessaria di esistenza di almeno una soluzione ammissibile per
un problema di MinCostFlow è che la somma dei flussi uscenti dalle sorgenti
sia uguale alla somma entrante nei pozzi:
b3
Σi∈V bi = 0
b4
-b3
t
-b4
21
Raffaele Pesenti
22
Generalizzazioni massimo flusso
Flusso a costo minimo
Commenti (cont.)
• Il problema di determinare una prima soluzione ammissibile per un problema
di massimo flusso con lower bound (anche negativi) può essere ridotto a un
problema di determinazione di un flusso ammissibile. E.g., determinare un
primo flusso ammissibile per la prima rete in figura
b =2
2 2
2
[0,4]
[0,5]
[0,4]
[0,5]
equivale a determinare un flusso
s
t
[0,1]
s
t
ammissibile per la seconda rete
[2,3]
[0,2]
[0,1]
[0,2]
[0,1]
1
1
b1=-2
[-∞,∞]
Problema del flusso a costo minimo MinCostFlow( G( V, E), b, l, u, c,min):
• Istanza : una rete orientata G( V, E) caratterizzata da: un valore intero bi
(flusso prodotto dal nodo) per ogni nodo i, un costo cij per flusso unitario e
delle capacità intere minime lij e massime uij per ogni arco (i,j)
• Soluzione : un flusso xij per ogni arco (i,j) t. c. rispetti le capacità date e che in
ogni nodo i siano soddisfatte le condizioni di bilanciamento, i.e., la somma
dei flussi uscenti del nodo sia uguale alla somma dei flussi entranti più il
flusso bi (eventualmente negativo) :
Σ(i,j)∈E xij = Σ (k,i)∈E xki + bi
lki ≤ xij ≤ uki
• Obiettivo : il costo totale del flusso sia minimo, i. e., min Σ(i, j)∈E cij xij
il flusso x(1,2) nella prima rete corrisponde a x’(1,2)+l(1,2), dove x’(1,2)
è il flusso nell’arco (1,2) nella seconda rete
Raffaele Pesenti
23
Raffaele Pesenti
24
Flusso a costo minimo
Flusso a costo minimo
Commenti:
In seguito si assumeranno, senza perdita di generalità, sempre vere le
seguenti condizioni
– tutti i dati sono interi
– tutti gli archi sono orientati
– tutti gli archi hanno costi non negativi (altrimenti basta invertire il senso
dell’arco e cambiare segno alle capacità dopo averle invertite)
– tutti gli archi hanno lower bound uguale a zero (altrimenti si eseguono le
trasformazioni indicate per i flussi massimi)
– i flussi dalle sorgenti e dai pozzi si compensano, i.e., Σi∈V bi = 0
– esiste sempre un percorso senza vincoli di capacità infinita tra ogni
coppia di nodi (altrimenti basta aggiungere archi artificiali di costo
infinito)
Raffaele Pesenti
25
Commenti (cont.)
Il problema MinCostFlow è risolvibile polinomilamente attraverso la
programmazione lineare.
Vale la pena di cercare se esistono caratteristiche specifiche del problema o
della sua soluzione che permettano lo sviluppo di algoritmi ad hoc di
risoluzione, più efficienti di quelli (general purpose) per la programmazione
lineare.
In quest’ottica si studiano inizialmente e le formulazioni primali e duali del
problema e quindi si introducono le reti residuali e gli pseudoflussi
Raffaele Pesenti
26
Totale unimodularità
Esempio formulazione PL
Al problema MinCostFlow(G( V, E),b,l,u,c,min)
in figura corrisponde:
min 2x(1,2) + 2x(1,3) + x(2,3) + 3x(2,4) + x(3,4)
π1:
π2:
π3:
π4:
-λ(1,2):
-λ(1,3):
-λ(2,3):
-λ(2,4):
-λ(3,4):
Raffaele Pesenti
x(1,2) + x(1,3) = 4
-x(1,2) + x(2,3) + x(2,4) = 0
-x(1,3) - x(2,3) + x(3,4) = 0
-x(2,4) - x(3,4) = -4
x(1,2) ≤ 4
x(1,3) ≤ 2
x(2,3) ≤ 2
x(2,4) ≤ 3
x(3,4) ≤ 5
x(i,j) ≥ 0 ∀ (i,j)
(cij, uij)
Totale unimodularità:
Una matrice è totalmente unimodulare (TU) se il determinante di ogni sua
sottomatrice quadrata assume valori 1, 0, -1
b(4) =-4
Proprietà:
• Una matrice A è TU se e solo se ha come elementi solo 1, 0 e -1 ed inoltre per
ogni sottoinsieme J ⊆ {1,…,n} delle colonne esiste una partizione J1, J2 t.c.:
b(2) =0
(2,4)
(3,3)
b(1) =4
(1,2)
(2,2)
∀i |Σj∈J1 aij - Σj∈J2 aij | ≤ 1
(1,5)
AT
• Se A è TU:
è TU, [A|I] è TU, cancellando o duplicando una riga/colonna di
A si ottiene una matrice TU, moltiplicando una riga/colonna per -1 si ottiene
una matrice TU, eseguendo un pivoting si ottiene una matrice TU.
• Determinare se una matrice è TU è polinomiale poiché ogni matrice TU può
essere ottenuta tramite tre tipi di composizione di cosiddette matrici network e
di due eccezioni.
b(3) =0
27
Raffaele Pesenti
28
Totale unimodularità
Esempio formulazione duale
Proprietà (cont.):
• Una matrice A è TU se e solo se, per ogni vettore intero b, tutti i vertici del
poliedro {x: Ax ≤ b, x ≥ 0} sono interi.
• La matrice di incidenza di un grafo orientato è TU.
• La matrice di incidenza di un grafo non orientato bipartito è TU.
• La matrice di incidenza di un grafo non orientato non bipartito non è TU.
Al problema MinCostFlow(G( V, E),b,l,u,c,min) in
figura corrisponde:
b(2) =0
max 4π1- 4π4 - 4λ(1,2)- 2λ(1,3)-2λ(2,3) -3λ(2,4) -5 λ(3,4)
Commenti:
• La matrice dei vincoli di un qualunque problema di MinCostFlow è TU in
quanto giustapposizione di una matrice di incidenza e da una matrice
identica.
• Esiste sempre un flusso intero ottimo soluzione di un problema di
MinCostFlow che ammetta soluzioni ottime finite
• I problemi che richiedano soluzioni intere e che, rilassando tale ipotesi, siano
formulabili come programmazione lineare continua con matrice dei vincoli
TU sono in P, in quanto si ottiene comunque una soluzione intera.
Raffaele Pesenti
(cij, uij)
29
π1 - π2 - λ(1,2) ≤ 2
(3,3)
(2,4)
b(1) =4
π1 - π3 - λ(1,3) ≤ 2
b(4) =-4
(1,2)
π2 - π3 - λ(2,3) ≤ 1
π2 - π4 - λ(2,4) ≤ 3
π3 - π4 - λ(3,4) ≤ 1
∀ (i,j)
λ(i,j) ≥ 0
πi libere
∀i
(2,2)
(1,5)
b(3) =0
Raffaele Pesenti
Costi ridotti
30
Costi ridotti
All’ottimo il costo ridotto associato al flusso xij dell’arco (i,j) vale
cij -πi + πj +λij ≥ 0
dove, per il teorema degli scarti complementari, se li flusso xij non satura la
capacità uij dell’arco si ha λij = 0. Posto cπij = cij -πi + πj si ha
– se xij = uij allora cij -πi + πj +λij = 0, quindi cπij = - λij, i.e., cπij≤ 0
– se 0< xij < uij allora cij -πi + πj +λij = 0, ma λij = 0, quindi cπij = 0
– se xij = 0 allora cij -πi + πj +λij ≥ 0, ma λij = 0, quindi cπij ≥ 0
viceversa
– se cπij< 0 allora xij = uij
– se cπij = 0 allora 0 ≤ xij ≤ uij
– se cπij > 0 allora xij = 0
Commenti:
• I valori πi associati ad ogni nodo vengono detti potenziali.
• Esistono tre classi di algoritmi di soluzione di problemi di MinCostFlow:
– algoritmi primali, a partire da un flusso ammissibile x si procede per
miglioramenti successivi mantenendo l’ammissibilità del flusso
– algoritmi duali, a partire da dei potenziali ammissibili π si procede per
ricercando un corrispondente flusso ammissibile mantenendo
l’ammissibilità (duale) dei potenziali
– algoritmi primali-duali, a partire da dei potenziali ammissibili π si
procede cercando di verificare le condizioni di scarto complementare.
I valori cπij = cij -πi + πj vengono anche essi detti costi ridotti, nel seguito con
tale termine si farà riferimento a questi ultimi.
Raffaele Pesenti
31
Raffaele Pesenti
32
Rete residuale
Rete residuale
Rete residuale:
Dato un problema MinCostFlow(G( V, E),b,l,u,c,min) e un flusso ammissibile x, si
definisce rete residuale la rete Gx(V’,E’) delle capacità residue (ancora utilizzabili)
una volta imposto il flusso x.
In Gx(V’,E’)
– V’ = V
– E’={(i,j): (i,j)∈ E or (j,i)∈ E}
– l’=0
– b’=0
– u’ij = uij - xij e c’ij = cij se (i,j)∈ E,
– u’ij = xij e c’ij = - cij se (j,i)∈ E,
(cij, uij)
Esempio:
Dato il problema MinCostFlow(G(V, E),b,l,u,c,min) e il flusso
b(2) =0
nella figura di destra, la corrispondente rete residuale risulta
essere come in figura sottostante
(2,4)
(3,3)
3
3
(-2,3)
b(1) =4
b(4) =-4
(1,2)
(-3,3)
(1,2)
1
1
(2,1)
(1,5)
(2,2)
(-2,1)
(1,4)
(2,1)
Raffaele Pesenti
33
xij
circuito negativo
Raffaele Pesenti
Algoritmo della cancellazione dei cicli
34
Circuiti negativi
Algoritmo della cancellazione dei cicli CycleCanceling (G(V, E),b,l,u,c)
1. Inizializzazione.
determinare flusso ammissibile x
2. Iterazione.
while Gx(V’,E’) contiene circuito negativo C {
δ =min{u’ij: (i,j)∈C}
xij= xij + δ
se (i,j)∈C, (i,j)∈E
xij= xij - δ
se (i,j)∈C, (j,i)∈E
xij= xij
se (i,j)∉C
}
Raffaele Pesenti
b(3) =0
(-1,1)
Teorema dei circuiti negativi:
Condizione necessaria e sufficiente di ottimalità di un flusso x è che non
esista alcun circuito negativo sulla corrispondente rete residuale.
Dimostrazione:
(necessità) Ovvia.
(sufficienza) Sia x* un flusso ottimo diverso da x. Il flusso differenza x* - x è
composto da uno o più flussi su cicli. Poiché x* - x può essere aggiunto a x
rispettando tutti i vincoli, allora x* - x deve potere essere realizzato sul grafo
residuale di x che però non ammette circuiti negativi. Ne consegue che cx* non può
essere minore di cx.
35
Raffaele Pesenti
36
(cij, uij)
Algoritmo della cancellazione dei cicli
Esempio
Commenti:
• Nell’ipotesi che esista sempre un percorso non vincolato in capacità tra ogni
coppia di nodi, il primo flusso ammissibile si può determinare attraverso la
soluzione di un problema di MaxFlow
• L’algoritmo ha un approccio primale, parte da una soluzione ammissibile che
migliora progressivamente e termina trovando il flusso ottimo (vedi teoremi
precedenti)
• L’algoritmo nella sua versione generale non è polinomiale, poiché nel caso
peggiore il costo diminuisce di un’unità ad ogni iterazione; l’algoritmo
compie un numero di iterazioni pari alla capacità massima di un arco per il
costo massimo di un arco, quindi la sua complessità è lineare nei parametri
del problema invece che essere logaritmica
• Scegliendo i circuiti a costo negativo in modo opportuno si possono avere
algoritmi polinomiali. In particolare scegliendo sempre il circuito con
minimo costo medio per arco si può sviluppare un algoritmo
O(min{n2m log(n), nm log(n max{cij}})
Raffaele Pesenti
37
b(2) =0
circuito negativo, δ=1
(2,4)
(3,3)
3
1
b(4) =-4
b(1) =4
(1,2) 2
1
3
(2,2)
(1,5)
b(3) =0
b(2) =0
Raffaele Pesenti
38
(-3,1)
(-2,3)
(2,1)
Pseudoflussi
(3,2)
(-1,2)
(-1,3)
(-2,1)
(1,2)
(2,1)
Pseudoflusso:
Uno pseudoflusso è un’assegnazione di valori alle variabili x t.c. siano
rispettati i vincoli sulle capacità e di non negatività ma non necessariamente i
vincoli di bilanciamento ai nodi.
(-2,2)
(2,4)
(3,3)
2
b(4) =-4
b(1) =4
(1,2) 2
2
4
(2,2)
(1,5) non esiste circuito
negativo⇒ottimo
b(3) =0
Raffaele Pesenti
b(2) =0
Esempio:
Sia dato il problema
(2,4)
(3,3)
3
3
MinCostFlow(G(V, E),b,l,u,c,min) e il
b(4) =-4
b(1) =4
flusso iniziale nella figura di destra,
(1,2)
1
1
xij
(-2,3)
(2,2)
(1,5)
(-3,3)
b(3) =0
(2,1)
b(2) =0
(1,2)
(2,4)
(3,3)
(-1,1)
3
1
b(4) =-4
b(1) =4
(-2,1)
(1,2) 2
1
3
(1,4)
(2,2)
(2,1)
(1,5)
b(3) =0
circuito negativo, δ=2
Sbilanciamento:
dato uno pseudoflusso x, per ogni nodo i è definito sbilanciamento il valore
(3,3)
(2,2)
ei= bi + Σ (k,i)∈E xki - Σ(i,j)∈E xij
– se ei > 0: ei è detto eccesso
– se ei < 0: -ei è detto deficit
(-1,2)
(-2,2)
(-1,4)
(1,1)
39
Raffaele Pesenti
40
Algoritmo dei percorso minimi successivi
Algoritmo dei percorsi minimi successivi
Algoritmo dei percorsi minimi successivi SuccShortestPath (G(V, E),b,l,u,c)
Commenti:
• La prima assegnazione dei valori dei potenziali π = 0 è banalmente ammissibile.
• Ad ogni assegnazione dei potenziali, che rimangono sempre ammissibili per il
duale, corrisponde uno pseudoflusso, non ammissibile dal punto di vista primale
tranne che all’ultima iterazione.
• L’algoritmo nella sua versione generale non è polinomiale, poiché nel caso
peggiore lo pseudoflusso corrente varia di un’unità ad ogni iterazione;
l’algoritmo compie un numero di iterazioni pari alla capacità massima di un arco,
quindi la sua complessità è lineare nei parametri del problema invece che essere
logaritmica.
• Scegliendo percorsi minimi in modo opportuno si possono avere algoritmi
polinomiali. In particolare, ad ogni iterazione, conviene scegliere i percorsi
considerando solo gli archi della rete residuale a capacità maggiore.
• In modo analogo si possono sviluppare algoritmi primali-duali. Il più noto tra essi
è l’out-of-kilter che opera su potenziali e flussi che inizialmente rispettano le
condizioni di bilanciamento ai nodi, ma non i vincoli sulle capacità
1. Inizializzazione.
x = 0; π = 0; e = b,
inizializzazione insiemi EC={i: e(i) >0}, DF ={i: e(i) <0},
2. Iterazione.
while EC≠∅ {
selezionare k∈ EC e j∈DF
determinare le distanze d minime, calcolate rispetto ai costi ridotti cπij,
da k a tutti gli altri nodi in Gx
determinare P(k,j) percorso minimo da k a j
π←π-d
δ =min{e(k),-e(j), u’ij: (i,j)∈ P(k,j)}
se (i,j)∈P(k,j), (i,j)∈E
xij= xij + δ
xij= xij - δ
se (i,j)∈ P(k,j), (j,i)∈E
xij= xij
se (i,j)∉ P(k,j),
aggiornare inoltre sbilanciamenti e costi ridotti
}
Raffaele Pesenti
41
Esempio
Esempio:
Sia dato il problema
MinCostFlow(G(V, E),b,l,u,c,min) e il
flusso iniziale nella figura di destra,
aggiornamento potenziali e costi ridotti
dopo il calcolo delle distanze minime
inizializzazione
e(2) =0, π(2) =0
(2,4)
e(1) =4
π(1) =0
(2-0+(-2),4)
e(1) =4
π(1) =0
(0,2)
e(4) =-4
π(4) =-3
e(1) =2
π(1) =0
(0,5)
percorso minimo, δ=2
e(3) =0, π(3) =-2
Raffaele Pesenti
(1,5)
e(4) =-2
π(4) =-3
(1,2)
(0,2)
2
2
pseudoflusso
e(3) =0, π(3) =-2 su rete originale
43
(0,4)
e(4) =-2
π(4) =-3
2
(0,5)
e(1) =2
π(1) =0
(2,3)
(-1,2)
(0,3)
e(3) =0, π(3) =-3
e(2) =0, π(2) =-2
e(2) =0, π(2) =-2
(0,4)
(2,3)
2
e(1) =0
π(1) =0
(0,2) 2
2
4
(0,5)
e(3) =0, π(3) =-3
Raffaele Pesenti
e(4) =-2
π(4) =-4
(0,2) (0,2)
e(3) =0, π(3) =-2
(-1,2)
(0,5)
2
e(2) =0, π(2) =-2
percorso minimo, δ=2
(2,3)
(1,2)
(0,2)
e(2) =0, π(2) =-2 aggiornamento
sbilanciamenti
(0,4)
(2,3)
(2,3)
(1,2)
e(1) =2
π(1) =0
e(3) =0, π(3) =0
e(2) =0, π(2) =-2
(0,4)
(0,4)
e(4) =-4
π(4) =0
(1,2)
42
e(2) =0, π(2) =-2
(cπij, uij)
(3,3)
(2,2)
d(2) = 2 ⇒ π(2) =0-2
Raffaele Pesenti
(0,2)
(2,3)
(0,2)
e(1) =0
e(4) =0
e(4) =0
π(4) =-4
π(1) =0
π(4) =-4
(0,2) (0,4)
sbilanciamenti nulli
(-1,2)
(0,1)
costi ridotti soddisfacenti
le condizioni di scarto
e(3) =0, π(3) =-3
complementare ⇒ ottimo
44
Algoritmo dei percorsi minimi successivi
Trasporto
Commenti:
• Ad ogni iterazione si risolve un problema di percorso minimo su una rete
residuale. Un problema di percorso minimo corrisponde a cercare un flusso
unitario che va da un nodo che presenta un eccesso ad un nodo che presenta un
deficit (vedere formulazione lineare del problema di percorso minimo). Lo
pseudoflusso così ottenuto viene quindi moltiplicato per il valore della capacità
minima che si incontra lungo il percorso per accelerare la ricerca della soluzione.
• Poiché ad ogni iterazione si considera la rete residuale, in cui sono stati
aggiornati gli sbilanciamenti e le capacità, gli pseudoflussi ottenuti si possono
sommare sulla rete originale mantenendo il rispetto delle capacità.
• Analogamente poiché le distanze minime cambiate di segno corrispondono ai
valori ottimi del duale del problema di percorso minimo, tali valori sono
ammissibili per il duale del problema di MinCostFlow e mantengono i costi
ridotti positivi a patto di ragionare su reti residuali.
Raffaele Pesenti
45
Problema del trasporto Transport( G( V1∪ V2, E), a, b, c,min):
• Istanza : una rete bipartita G( V1 ∪ V2, E) caratterizzata da un valore intero ai
non negativo (disponibilità prodotto) per ogni nodo i∈V1, un valore intero bj
non negativo (richiesta prodotto) per ogni nodo j∈V2, un costo cij di trasporto
per ogni unità di prodotto per ogni arco (i,j)∈ E, con i∈V1 e j∈V2
• Soluzione : un flusso xij per ogni arco (i,j) t.c. in ogni nodo j ∈V2 sia
soddisfatta la richiesta di prodotto bj e in ogni nodo i∈V1 non sia violata la
disponibilità ai,
• Obiettivo : il costo totale del trasporto sia minimo, i. e., Σ(i, j)∈E cij xij
Raffaele Pesenti
Esempio formulazione PL
min 8x11 + 7x12 + 4x13 + 5x21 + 2x22 + 9x23
x11 + x12 + x13 ≤ 10
x21 + x22 +x23 ≤ 15
x11 + x21 = 7
x12 + x22 = 5
x13 + x23= 12
xij ≥ 0 ∀ (i,j)
c11= 8
c21= 5
aggiungendo un nodo di richiesta con domanda
uguale a Σi∈V1 ai - Σj∈V2 bj e con costi di trasporto
nulli si bilancia domanda e offerta e si riduce il
problema ad un problema di flusso a costo minimo:
c11= 8
c21= 5
a1=10
c12= 7
a1=10
b2=5
c22= 2
min 8x11 + 7x12 + 4x13 + 5x21 + 2x22 + 9x23
c12= 7
b2=5
c22= 2
a2=15
c13= 4
c23= 6
b3=12
Raffaele Pesenti
b1=7
Esempio formulazione PL
b1=7
Al problema Transport( G( V1∪ V2, E), a, b, c,min)
in figura corrisponde:
46
47
vincolo
ridondante
Raffaele Pesenti
x11 + x12 + x13 + x1s = 10
x21 + x22 +x23 +x2s = 15
x11 + x21 = 7
x12 + x22 = 5
slack
x13 + x23= 12
x1s + x2s= 1
xij ≥ 0 ∀ (i,j)
a2=15
c13= 4
c23= 6
b3=12
c2s= 0
c1s= 0
bs=1
48
Esempio
Trasporto
bC=7
cAC= 3
Esempio:
Risoluzione con l’algoritmo dei percorsi
minimi successivi il problema di
Transport( G( V1∪ V2, E), a, b, c,min)
in figura
cBC= 10
aA=5
cAD= 1
bD=2
cBD= 3
aB=10
cAE= 5
cBE= 10
bE=6
Raffaele Pesenti
49
Commenti:
• L’aggiunta del nodo che bilancia domanda e offerta corrisponde
all’introduzione delle variabili di slack per formulare il problema in forma
standard e all’aggiunta di un vicolo ridondante.
• Il problema di trasporto, in quanto riducibile ad un problema di
MinCostFlow, è un problema in P e viene risolto con gli algoritmi di
soluzione di quest’ultimo problema (eventualmente specializzati).
• Se la rete associata al problema di trasporto è bipartita completa (i.e., se ogni
possibile assegnazione è ammissibile, eventualmente con costo molto
elevato) e se Σi∈V1 ai = Σj∈V2 bj allora il problema di trasporto ammette
sempre almeno una soluzione ammissibile.
• Un caso particolare del problema di trasporto è il problema di assegnazione
(vedi in seguito).
Raffaele Pesenti
Esempio
Esempio
Commenti:
• Nell’algoritmo dei percorsi minimi successivi si definiscono successivamente dei
valori πi che soddisfano la formulazione duale.
πi - πj ≤ cij
e che equivale ad imporre che i costi ridotti siano non negativi
cπij = cij -(πi - πj ) ≥ 0
• Ad ogni passo si determina un nuovo pseudoflusso (uno lungo un cammino
minimo della rete residuale) in modo che si possano aggiornare i potenziali
permettendo loro di essere ammissibili per la formulazione duale del problema e di
rispettare le condizioni di scarto complementare
xij > 0 ⇒ cπij= 0
cπij > 0 ⇒ xij= 0
dove xij è la combinazione degli pseudoflussi ottenuti fino ad allora.
• Ad ogni iterazione si riduce lo sbilanciamento della rete.
Formulazione primale PL come MinCostFlow
min 3xAC + xAD + 5xAE + 10xBC + 3xBD + 10xBE
xAC + xAD + xAE = 5
xBC + xBD + xBE = 10
−xAC - xBC = -7
−xAD - xBD = -2
-xAE - xBE= -6
xij ≥ 0 ∀ (i,j)
Nell’algoritmo dei percorsi minimi
successivi si definiscono successivamente
dei valori πi che soddisfano la formulazione
duale (e quindi che impongono che i costi
ridotti siano non negativi)
Raffaele Pesenti
50
Formulazione duale PL
max 5πA +10πB - 7πC - 2πD - 6πE
πA
πA
πA
πB
πB
πB
πi
- πC ≤ 3
- πD ≤ 1
- πE ≤ 5
- πC ≤ 10
- πD ≤ 3
- πE ≤ 10
libera ∀ i
51
Raffaele Pesenti
52
Inizializzazione
rete originale = rete residuale
fine prima iterazione
eC=-7
aggiornati π ed e πC=-3
eC=-7
πC=0
cπBC= cBC= 10
cπAC= cAC= 3
π
cπBD= cBD = 3 c AD= cAD = 1
0
eD=-2
πD=0
cπAE= cAE= 10
2+M
0
2
eA=3
πA=0
5+M
eB=10
πB=0 -M
cπAE= cAE = 5
eB=10
πB=0-2M
eD=0 0
πD=-1
2+2M
0
eE=-6
πE=-5
0
2M
Raffaele Pesenti
fine quarta iterazione
eC=-2
πC=-10
0
(0,5)
5
5
0
2
eA=0
πA=-2-2M
eB=8
πB=0
0
0
eA=0
πA=-2
eE=-6
55
Raffaele Pesenti
eB=2
πB=0
5
0
2
5
0
2
eA=0
πA=-7
6
0
πE=-7
0
eD=0
πD=-3
eD=0 0
πD=-3
0
3
eE=-6
πE=-7-2M
0
54
πC=-5
eD=0
tutti i potenziali presentano una componente
2M, ma poiché interessano solo le differenze
tra i potenziali, essa può essere trascurata
eA=0
πA=0
eE=-6
C
πD=-3-
3
0
πE=-5
rete residuale
costi ridotti sempre nulli
sugli archi dove passa
pseudoflusso
e =-2
eC=-2
5
5+2M
(0,2)
0
3
2
Raffaele Pesenti
(0,2)
5+2M
2+2M
eE=-6 (costo rid., capacità)
πC=-5-2M
0
eB=10
eD=0
πD=-1
πA=0 πB=0-2M
πE=-5
fine terza iterazione
eB=8
eA=0
πA=0 πB=0-2M
eA=3
0
0
eE=-6
53
(0,3)
0
5+M
πE=-5
Raffaele Pesenti
7+2M
eD=0
πD=-1
pseudoflusso
il nodo B non è fortemente connesso ad A
convenzionalmente si assume che disti M,
dove M è una distanza maggiore di
qualunque altra sulla rete
rete residuale
potenziali ammissibili per il
duale dato che i costi ridotti
sono sempre non negativi
eC=-4
πC=-3
2+M
7+2M
0
(0,2)
0
percorso minimo
eE=-6
πE=0
πC=-3
7+M
7+M
πD=-1
eA=5 eB=10
πA=0 πB=0-M
eC=-4
eC=-7
πC=-3
eD=0
eB=10
πB=0
fine seconda iterazione
rete residuale
eE=0
πE=-10
56
fine quinta iterazione
rete residuale
Trasporto: esempio soluzione con circuiti negativi
rete bilanciata,
si è giunti all’ottimo
eC=-2
πC=-10
eC=0
πC=-10
0
(0,5)
0
0
2
eD=0 0
πD=-3
5
0
eB=2
πB=0
eB=0
eA=0
πB=0
πA=-7
(0,2)
Esempio dell’uso dell’algoritmo di cancellazione dei circuiti negativi
applicato al seguente problema di trasporto.
Transport( G( V1∪ V2, E), a, b, c,min):
5
eD=0
πD=-3
0
2
5
0
2
eA=0
πA=-7
6
0
V1 = {A, B, C}: tre sorgenti con capacità rispettivamente uguali a a = (12, 7, 9)
V2 = {D, E, F}: tre pozzi con domanda rispettivamente uguali a b = (8, 11, 9)
E = {AD, AE, AF, BD, BE, BF, BD, BE, BF}: connessioni che uniscono tutte le
sorgenti a tutti i pozzi, con costo unitario di trasporto rispettivamente uguale
a c = (4, 3, 5, 7, 5, 4, 6, 10, 9)
2
(0,6)
eE=0
eE=0
πE=-10
πE=-10
Raffaele Pesenti
57
Raffaele Pesenti
Esempio
costi trasporto
unità di flusso
5
Esempio
4
A
12
4
F
D
5
9
capacità sorgenti
Raffaele Pesenti
min 4xAD + 3xAE + 5xAF + 7xBD + 5xBE + 4xBF+ 6xCD + 10xCE + 9xCF minimizzazione costi
xAD + xAE + xAF ≤ 12
vincoli sulle capacità delle sorgenti
xBD + xBE +xBF ≤ 7
xCD + xCE +xCF ≤ 9
xAD+ xBD + xCD = 8
xAE + xBE + xCE = 11
vincoli di soddifacimendo delle domande
xAF + xBF + xCF = 9
xij ≥ 0 ∀ (i,j)
7
B
9
domanda pozzi
Formulazione del problema di trasporto come problema PL.
Si osservi che i valori assunti dalla generica variabile decisionale xij corrisponde al flusso
che si deve trasportare da I a J se si vuole minimizzare i costi di trasporto soddisfando la
domanda dei pozzi senza violare la capacità delle sorgenti
8
3
7
9
C
58
11
E
10
6
Segue risoluzione del problema di trasporto con l’algoritmo dei circuiti negativi
59
Raffaele Pesenti
60
Esempio
Esempio
inizializzazione
rete residuale
flussi ammissibili
definiti nel rispetto
dei vincoli, ma senza 9
cercare di
minimizzare i costi
5
4
A
12
8
D
3
4
F
7
7
5
capacità e
costi archi
inversi
9
9
5
9
9
costo:
3×3+5×9+5×7+10×1+6×8 = 147
10
7
E
6
61
10
A
9
F
4
-6
62
Raffaele Pesenti
-5
10
1
-3
5
8
D
3
F
8
4
A
12
8
4
3
7
B
C
6
Raffaele Pesenti
flussi ammissibili
definiti dalla somma
algebrica tra i flussi
iniziali e quelli del
circuito negativo
D
5
costo circuito negativo:
3-10+9-5 =-3
capacità circuito:
9
min{9,1} = 1
diminuzione costo ottenibile:
-3 ×1 = -3
E
-10
Esempio
7
4
8
-3
nuovi flussi
3
-5
1
C
Esempio
5
-5
8
Raffaele Pesenti
circuito negativo
3
7
5
9
C
-6
B
11
1
D
7
4
F
B
4
3
-5
3
A
7
7
4
B
9
5
7
11
1
E
-10
9
9
C
nuovo costo:
3×4+5×8+5×7+9×1+6×8 =144 = 147-3
6
63
Raffaele Pesenti
E
10
6
8
64
Esempio
rete residuale
4
A
5
Esempio
8
circuito negativo
-5
8
-5
5
-9
9
-5
1
F
8
-3
C
6
Raffaele Pesenti
65
5
9
1
1
F
7
4
7
Raffaele Pesenti
66
8
-5
9
C
nuovo costo:
3×11+5×1+4×7+9×1+6×8 =123 = 144-21
-6
7
E
1
La rete residuale non ha circuiti negativi.
I flussi nel lucido precedenti sono ottimi
67
Raffaele Pesenti
5
7
-9
8
11
B
-4
11
6
D
4
F
10
4
3
11
1
Raffaele Pesenti
1
D
5
9
A
5
B
9
6
Esempio
3
7 4
E
10
rete residuale
5
-38
-5
C
Esempio
nuovi flussi
A
12
4
7
B
costo circuito negativo:
3-5+4-5 =-3
capacità circuito:
-9
min{7,8} = 7
diminuzione costo ottenibile:
-3 ×7 = -21
E
10
7
4
4
7
B
D
-6
3
-6
7
4
F
5
D
3
4
A
9
-5
8
E
10
C
-3
6
68
Esempio formulazione PL
Assegnazione
A
Problema di assegnazione AP(V1,V2,c,min):
• Istanza : due insiemi V1, V2 t.c. |V1|=|V2| e un costo valore cij per ogni coppia
di elementi (i,j) t.c. i∈V1 e j∈V2 che rappresenta il costo di assegnazione
dell’elemento imo a quello jmo (e.g., del lavoratore imo al compito jmo).
• Soluzione : una funzione di assegnazione xij: V1×V2 →{0,1} che, per ogni
coppia (i,j), valga 1 se i è assegnata a j, 0 altrimenti
• Obiettivo : il costo totale delle assegnazioni sia minimo, i. e., Σ(i, j)∈E cij xij
Raffaele Pesenti
69
Al problema AP(V1,V2,c,min) in figura corrisponde:
min 8xAD + 7xAE + 4xAF + 5xBD + 2xBE + 9xBF +
+ 7xCD + 9xCE + 4xCF
xAD + xAE + xAF = 1
xBD + xBE +xBF = 1
xCD + xCE +xCF = 1
xAD + xBD + xCD = 1
xAE + xBE + xCE = 1
xAF + xBF + xCF = 1
xij ∈{0,1} ∀ (i,j)
Raffaele Pesenti
cAF= 4
cBD= 5
cBE= 2
B
E
cBF= 9
cCD= 7
cCE= 2
C
F
cCF= 4
70
Esempio
71
D
cAE= 7
Raffaele Pesenti
Assegnazione
Commenti:
• Data la totale unimodularità della matrice dei vincoli, la condizione xij ∈{0,1} può
essere rilassata in 0≤ xij ≤1, ottenendo comunque soluzioni binarie.
Inoltre, poiché xij ≤1 è già implicato dagli altri vincoli, la condizione xij∈{0,1} può
essere rilassata in xij≥0 ottenendo comunque un problema equivalente a quello
originale
• La formulazione in forma di problema di programmazione lineare e le
considerazioni precedenti evidenziano come un problema AP(V1,V2,c,min) possa
essere considerato come un caso particolare di problema di trasporto in cui ogni
disponibilità e richiesta sono unitari Transport(G(V1∪V2,E),1,1,c,min).
• Il problema di trasporto, in quanto riducibile ad un problema di MinCostFlow, è un
problema in P e viene risolto con gli algoritmi di soluzione di quest’ultimo problema
(eventualmente specializzati). Un algoritmo molto noto è detto ungherese ed è un
algoritmo primale-duale. L’algoritmo dei percorsi minimi successivi, che nel caso
del MinCostFlowè pseudopolinomiale poiché lineare nella capacità degli archi,
risulta polinomiale per AP poiché in questo caso la capacità massima è 1.
cAD= 8
Esempio:
Risoluzione con l’algoritmo dei circuiti
negativi il problema di AP(V1,V2,c,min)
in figura
A
cAD= 8
D
cAE= 7
cAF= 4
cBD= 5
cBE= 2
B
E
cBF= 9
cCD= 7
cCE= 2
C
F
cCF= 4
Raffaele Pesenti
72
rete residuale
inizializzazione
fine prima interazione
assegnazione ammissibile, volutamente pessima,
si sarebbe potuto partire da una migliore, e.g., greedy
8
7
5
4
2
-8
(1)
2
5
4
9
7
8
7
(uBD=1)
-9
nel problema di assegnazione tutte le capacità
degli archi sono unitarie come tutti i flussi entranti
o uscenti dai nodi, quindi sono omessi nel disegno
Raffaele Pesenti
73
rete residuale
2
9
7
-2
(-1)
5
4
2
7
4
7
2
4
4
circuito negativo
nuova assegnazione
(su rete originale)
Raffaele Pesenti
74
rete residuale
fine seconda interazione
fine terza interazione
non esistono circuiti negativi!
-8
8
8
7
4
5
9
-4
circuito negativo
Raffaele Pesenti
9
-5
9
7
7
4
2
2
7
2
5
-4
4
-2
7
7
8
7
4
4
nuova assegnazione
(su rete originale)
2
9
7
-2
2
5
2
4
assegnazione ottima
75
Raffaele Pesenti
76
Simplesso su reti
Simplesso su reti
Concetti base:
• Dato un problema MinCostFlow si dicono soluzioni ad albero ricoprente
(spanning tree solutions) un insieme di flussi ammissibili che per ogni arco
(i,j) che non appartiene ad un albero ricoprente* dato o sono nulli o sono
uguali alla capacità dell’arco, per ogni arco (i,j) appartenente all’albero dato
possono essere determinati in modo univoco.
• Un problema MinCostFlow se ha soluzioni ammette sempre una soluzione
ottima ad albero ricoprente.
• E’ possibile determinare la soluzione ottima ad albero ricoprente muovendosi
da un albero ricoprente all’altro aggiungendo ad ogni passo un nuovo arco
all’albero corrente ed eliminandone uno appartenente ad esso. Ogni albero
corrisponde ad una soluzione di base ammissibile, mentre lo scambio di archi
corrisponde ad un’operazione di pivot. La scelta degli archi che “entrano ed
escono dalla base” è effettuata in modo opportuno in modo da evitare il
rischio di cycling.
Premesse:
• Il problema MinCostFlow è formulabile come un problema di
programmazione lineare.
• Il simplesso ha in generale prestazioni estremamente efficienti, ma non
sfrutta la struttura a rete del problema MinCostFlow.
Conseguenze:
• E’ stato sviluppato l’algoritmo network simplex che basandosi sulle stesse
idee del simplesso sfrutta la struttura a rete.
• Pur essendo nel caso peggiore esponenziale, tale algoritmo ha in media
prestazioni concorrenziali con i migliori algoritmi polinomiali per il
problema di MinCostFlow.
* vedere lucidi successivi
Raffaele Pesenti
77
Raffaele Pesenti
78
Alberi
Bibliografia
• Un grafo è aciclico se non contiene cicli (orientati o non)
• Un albero è un grafo non diretto connesso ed aciclico
• Ogni grafo aciclico è in generale l’unione di alberi e viene detto foresta
La bibbia per problemi di flusso su reti
(da dove sono stati tratti esempi ed esercizi)
R. K. Ahuja, T. L. Magnanti, J. B. Orlin
Network Flow
Prentice Hall, Englewood Cliffs, NJ, (1993)
grafo aciclico
(foresta)
albero
Il miglior software per reti
LEDA
Raffaele Pesenti
grafo non aciclico
79
Raffaele Pesenti
80
Alberi
Alberi
• Dato un albero T=(V,E), si dice foglia un nodo v∈V tale cheδ(v)=1
(w(v)=1 )
• Se V≥2 allora esistono almeno due foglie
• Dato G=(V,E), si dice albero ricoprente (spanning tree) di G un albero
T=(W,F) con W=V ed F⊆E (è un sottografo di G)
Proprietà:
• Dato G=(V,E), le seguenti affermazioni sono equivalenti:
• G è un albero
• ogni coppia di nodi di G è connessa da un unico cammino
• G è aciclico eE=V-1
• G è aciclico e connettendo due nodi non adiacenti con un arco si ottiene
un grafo con un unico ciclo
• G è connesso eE=V-1
• La matrice di incidenza di un albero è composta da n - c colonne, dove c è il
numero di componenti connesse dell’albero, e ha rango massimo.
Tutte le proprietà precedenti si possono dimostrare per induzione sulla
dimensione del grafo a partire da un grafo composto di due soli nodi.
Raffaele Pesenti
foglie di un albero
81
Raffaele Pesenti
82
Algoritmo di Kruskal
Albero ricoprente minimo
Problema dell'albero ricoprente minimo(Minimum Spanning Tree) MST(G(V,E),c, min):
Istanza: data una rete G(V,E) non orientata caratterizzata da costi c sugli archi.
Soluzione: un albero ricoprente T(V,F)
Obiettivo: minimo costo dell’albero, i.e., min Σ(i,j)∈F c(i,j)
Commenti:
• MST è in P, in quanto esistono algoritmi polinomiali (e.g., Kruskal, Prim) che lo
risolvono all’ottimo, non è banalmente riconducibile alla programmazione lineare
come i problemi di flusso
• Applicazioni
– determinare la rete di comunicazione più affidabile
– determinare la connessione tra n centri a costo minimo (e.g., distribuzione del
gas)
Raffaele Pesenti
un albero ricoprente
83
Algoritmo KruskalMST(G(V,E),c)
1. inizializzazione:
Si ordinano gli archi e1, e2,..., em in modo che i costi associati non siano decrescenti (c1≤c2≤... ≤cm).
Si inizializza l'insieme F0=∅, k=1 e la foresta T0=(V,∅ )
tutti i nodi sono marcati con nil
2. iterazione:
forall ek ∈E {
if se gli estremi ek sono marcati nil o con due valori diversi //(V, Fk-1∪ {ek}) è una rete aciclica,
si pone Tk=(V, Fk) con Fk=Fk-1∪{ek}
si marcano i nodi connessi dall’aggiunta di ek
else Fk=Fk-1 e Tk= Tk-1
if Fk=n-1 return
//Tk è l’albero ricoprente cercato,
else k=k+1
}
Raffaele Pesenti
84
Algoritmo di Kruskal
Algoritmo di Kruskal
14
7
Esempio:
n=9
m=17
4
10
8
11
Commenti:
• L’algoritmo di Kruskal è greedy (ingordo), ad ogni passo esegue la scelta
marginalmente ottima senza preoccuparsi delle conseguenze future.
• L’algoritmo è ottimo (vedi in seguito)
• La fase di inizializzazione dell’algoritmo richiede l’ordinamento di m archi ed è quindi
O(mlogm). La fase di iterazione esegue il ciclo al più m volte in cui compie operazioni
in tempo O(1) a parte la fase di marcatura che complessivamente in tutti i cicli non
richiede più di O(n2) operazioni.
• Un possibile algoritmo di marcatura è infatti il seguente in cui marca i nodi con un
numero tra 0 e (n-1)/2 secondo le seguenti regole
9
17
12
3
6
13
2
5
1
16
– se entrambe i nodi sono marcati nil marcarli con il minimo numero non utilizzato
– se uno dei nodi è marcato e l’altro è nil, marcare quest’ultimo con il numero dell’altro
– se tutti e due i nodi sono marcati, marcare tutti i nodi dell’albero connesso al nodo con
valore maggiore.
15
la procedura di marcamento è O(n2) poiché al termine dell’algoritmo tutti i nodi sono
marcati 0 e al più ogni nodo viene rimarcato (n-1)/2 volte. Usando opportune
strutture dati si possono ottenere procedure di verifica di ciclicità anche più efficienti.
Raffaele Pesenti
85
Raffaele Pesenti
Algoritmo di Prim
86
Algoritmo di Prim
Algoritmo PrimMST(G(V,E),c)
10
Esempio:
n=6
m=12
1. inizializzazione:
Si sceglie un vertice arbitrario di G, V0={s}, si pone F0=∅ e k=1
9
8
7
2. iterazione:
12
while Fk <n-1{
si connette un nodo i∈Vk-1 con un nodo h∈V- Vk-1 tale che il costo dell’arco (i,h) sia
c ih =
min
i∈ V k − 1 , j∈ V − V
( i , j )∈ E
k −1
[c ( i ,
7.5
11
16
19
10.5
9.5
Commenti:
• L’algoritmo di Prim è O(V2) è più efficiente di quello di Kruskal (O(ElogE))
nel caso peggiore (può convenire Kruskal se la rete è sparsa).
• Questo algoritmo si basa sul fatto che un albero ricoprente è minimo se e solo se,
per ogni arco (i,j) appartenente ad esso, si verifica che cij ≤ cpq per ogni arco (p,q)
appartenente al taglio formatosi dalla cancellazione di (i,j) dall’albero.
j)]
si pone Vk=Vk-1∪ {h} e Fk=Fk-1∪ {(i,h)}
k=k+1
}
return // l’algoritmo si ferma per Fk=n-1, T=(Vk,Fk) è l’albero ricoprente cercato,
Raffaele Pesenti
17
87
Raffaele Pesenti
88
G-19
Formulazione PL
Esempio formulazione in PL
Al problema MST(G(V,E),c,min) in figura corrisponde:
Al problema MST(G(V,E),c, min) corrisponde:
min x12 + 3x13 + 2x23 + 4x24 + 4x34
min Σ(i, j)∈E cij xij
Σ(i, j)∈E xij = |V| -1
Σ(i, j)∈E(S) xij ≤ |S| -1
x12 + x13 + x23 + x24 + x34 = 3
S={1,2}
x12 ≤ 1
S={1,3}
x13 ≤ 1
x23 ≤ 1
S={2,3}
S={2,4}
x24 ≤ 1
x34 ≤ 1
S={3,4}
x12 + x13 +x23 ≤ 2
S={1,2,3}
S={1,2,4}
x12 + x24 ≤ 2
x13 + x34 ≤ 2
S={1,3,4}
S={2,3,4}
x23 + x24 +x34 ≤ 2
xij ∈{0,1} ∀ (i,j)
// vincolo di cardinalità
∀S⊂V // vincoli di packing
xij ∈{0,1} ∀ (i,j)
dove E(S) è l’insieme degli archi della sottorete indotta dal sottoinsieme dei
nodi S. I vincoli sono significativi ovviamente solo per |S| ≥ 2
Raffaele Pesenti
89
1
4
4
2
3
3
4
Raffaele Pesenti
Formulazione PL
90
Formulazione PL
Commenti:
• Il numero di vincoli è esponenziale.
• La condizione xij∈{0,1} può essere rilassata in xij≥ 0 ottenendo comunque un
problema equivalente a quello originale.
• Il problema può essere risolto attraverso l’uso di un oracolo di separazione:
– Si considera inizialmente solo un sottoinsieme dei vincoli di packing e si
determina la soluzione ottima del problema corrispondente;
– la soluzione corrente è quindi valutata da un algoritmo (detto oracolo)
che o ne certifica l’ammissibilità (e quindi l’ottimalità) per il problema
originario o restituisce almeno uno dei vincoli violati;
– se la soluzione non è ammissibile si aggiunge il vincolo fornito
dall’oracolo a quelli inizialmente considerati e si itera.
• L’approccio che usa un oracolo di separazione è un approccio duale. Esso si
base sull’idea che ad ogni passo del simplesso duale non è necessario
considerare tutti i vincoli, ma basta individuarne uno che venga violato dalla
soluzione corrente.
Raffaele Pesenti
2
1
91
Commenti:
• Vale il teorema dimostrato da Grötschel (1988):
Dato un problema di ottimizzazione rispetto a dei vincoli definiti da un
sistema di disequazioni, il problema è risolvibile in tempo polinomiale se e
solo se:
– l’oracolo di separazione è realizzabile attraverso un algoritmo polinomiale,
– il numero di cifre dei coefficienti dei vincoli generati cresce in modo
“sufficientemente” lento.
Dimostrazione: si basa sull’utilizzo del metodo dell’elissoide.
• Ne consegue che qualunque problema (in questo caso MST ) per cui è
definibile un algoritmo di separazione polinomiale è P-easy, anche nel caso
in cui la sua formulazione richieda un numero esponenziale di vincoli.
Raffaele Pesenti
92
Esempio formulazione in PL con oracolo
Al problema MST(G(V,E),c,min) in figura corrisponde inizialmente:
min x12 + 3x13 + 2x23 + 4x24+ 4x34
x12 + x13 + x23 + x24 + x34 = 3
S={1,2}
x12 ≤ 1
S={1,3}
x13 ≤ 1
x23 ≤ 1
S={2,3}
S={2,4}
x24 ≤ 1
x34 ≤ 1
S={3,4}
xij ≥ 0 ∀ (i,j)
Esempio formulazione in PL con oracolo
2
1
1
4
3
2
1
1
Soluzione correntemente ottima: x12 = x13 = x23 = 1, x24 = x34 =0,
soluzione inammissibile poiché forma il ciclo 1,2,3 e che viola il
vincolo x12 + x13 +x23 ≤ 2
4
2
3
soluzione
corrente
nuovo problema ottenuto dall’aggiunta del vincolo violato:
4
4
4
2
3
Raffaele Pesenti
4
3
93
min x12 + 3x13 + 2x23 + 4x24 + 4x34
x12 + x13 + x23 + x24 + x34 = 3
S={1,2}
x12 ≤ 1
S={1,3}
x13 ≤ 1
x23 ≤ 1
S={2,3}
S={2,4}
x24 ≤ 1
x34 ≤ 1
S={3,4}
x12 + x13 +x23 ≤ 2
S={1,2,3}
xij ≥ 0 ∀ (i,j)
soluzione
ottima
2
1
1
4
4
2
3
4
3
Soluzione correntemente ottima: x12 = x23 = x34 = 1, x13 = x24 =0,
soluzione ammissibile poiché non forma cicli e quindi ottima.
Raffaele Pesenti
94
Esempio formulazione in PL con oracolo
Matroidi
Commenti:
• La realizzazione di un oracolo di separazione è nel caso del problema
dell’albero ricoprente minimo facile anche perché si può dimostrare che un
qualunque problema che consideri solo un sottoinsieme dei vincoli di
packing e il vincolo rilassato xij ≥ 0 ∀ (i,j) ha soluzione ottima binaria. Basta
quindi verificare che la sottorete definita dagli archi associati alle soluzioni
xij=1 sia aciclico o meno. Nel caso tale sottorete non sia aciclica un vincolo
certamente violato è quello che corrisponde all’insieme dei nodi inclusi in
uno dei cicli esistenti.
• Determinare un ciclo in una rete può essere determinato con un algoritmo
O(m)
Premessa:
Il problema dell’albero ricoprente minimo può essere risolto per mezzo di un
algoritmo greedy.
In seguito verranno illustrate quali caratteristiche dell’albero ricoprente
permettono il verificarsi di tale “fortunata” condizione.
Raffaele Pesenti
95
Raffaele Pesenti
96
Matroidi
Matroidi
Insiemi indipendenti:
Un sistema di sottoinsiemi (N, I), i.e., N un dato insieme (e.g., l’insieme
degli archi di un grafo G) e I è una collezione di sottoinsiemi di N che
godono di una data proprietà (e.g., i sottoinsiemi degli archi di G che
formano degli alberi o foreste), è detto sistema indipendente se F1∈I e F2⊆F1
implica F2∈I. I sottoinsiemi in I sono detti insiemi indipendenti, gli altri
sottoinsiemi di N sono detti insiemi dipendenti.
Matroidi:
Un insieme indipendente (N, I) è detto matroide se soddisfa anche la
proprietà di crescita, i.e., se Fp e Fp+1 sono insiemi indipendenti in I di p e
p+1 elementi rispettivamente allora è sempre possibile determinare un
elemento e∈ Fp+1- Fp t.c. Fp∪{e} è un insieme indipendente.
Raffaele Pesenti
97
Commenti:
• Gli insiemi indipendenti massimali di un matroide hanno la stessa cardinalità
(questa proprietà è utilizzata per dare una definizione alternativa di matroide)
• Dato un grafo G gli insiemi degli archi che definiscono degli alberi o delle
foreste in G soddisfano la definizione di matroide. Gli alberi ricoprenti sono
gli insiemi indipendenti massimali.
• Data un matrice A gli insiemi delle colonne linearmente indipendenti
soddisfano la definizione di matroide. Le basi della matrice sono gli insiemi
massimali.
Raffaele Pesenti
Insieme indipendente massimale di peso minimo
98
Algoritmo greedy
Algoritmo greedy((N, I), c)
Problema del insieme indipendente massimale di peso minimo
(Minimum-Weight Independent Set) MinIndSet((N, I), c, min):
Istanza: dato un matroide (N, I) caratterizzato da costi ce per ogni elemento e
in N.
Soluzione: un insieme indipendente massimale F incluso in I
Obiettivo: minimo costo dell’insieme F, i.e., min Σe∈F ce
1. inizializzazione:
Si ordinano gli elementi e1, e2,..., em in modo che i costi associati non siano
decrescenti (c1≤c2≤... ≤cm).
Si pone F0=∅, k=1
2. iterazione:
while k < |N| {
si sceglie ek,
if Fk-1∪{ek} è un iniseme indipendente Fk=Fk-1∪{ek},
else Fk=Fk-1
}
return // per k = |N|, Fk è l’insieme indipendente cercato
Raffaele Pesenti
99
Raffaele Pesenti
100
Algoritmo greedy
Matching
Proprietà:
• L’algoritmo greedy risolve all’ottimo il problema MinIndSet.
• Se il sistema indipendente (N, I) non è un matroide esistono dei valori di c per
cui l’algoritmo greedy non è ottimo.
Dimostrazione (prima proprietà)
Sia Fn={ek1, ek2, …, ekj,... ,ekn} l’insieme indipendente ottenuto dall’algoritmo greedy e
F* l’insieme indipendente ottimo, siano inoltre gli elementi dei due insiemi ordinati per
pesi crescenti. Sia il jmo il primo elemento differente nei due insiemi, l’insieme
F’={ek1, ek2, …, ekj} in quanto incluso in Fn è indipendente, analogamente è
indipendente l’insieme F’*={ek1, ek2, …, eq} composto dai primi j elementi di F*.
Poiché Fn è stato definito in modo greedy ckj≤ cq, quindi il peso degli elementi di F’ è
non superiore a quello degli elementi di F’*. Per la proprietà di crescita si possono
aggiungere a F’ gli altri elementi di F* (non già inclusi in F’) ottenendo un insieme
indipendente massimale F”. Gli elementi di F” hanno peso complessivo non superiore a
quello degli elementi di F* e differiscono da Fn al più a partire dall’(j+1)mo elemento.
Iterando il ragionamento si giunge ad ottenere un insieme indipendente ottimo
coincidente con Fn.
Raffaele Pesenti
101
Premessa:
Si sono visti problemi in P che o sono facilmente riducibili a problemi di
programmazione lineare oppure sono comunque risolvibili con algoritmi
“banali”.
Esistono altri problemi in P che non soddisfano nessuna delle due condizioni
precedenti. I più noti tra essi sono i problemi di matching.
Matching:
Dato un grafo G(V,E) un matching (accoppiamento) è un sottoinsieme M
degli archi in E t.c. nessuna coppia di archi in M incida su un nodo comune.
Commento:
Un matching accoppia nodi fra loro.
Raffaele Pesenti
102
Problemi di matching
Esempio di matching
Problema del matching di cardinalità massima MaxCardMatching (G(V,E),max):
Istanza: un grafo non orientato G(V,E).
Soluzione: un matching M di G
Obiettivo: massima cardinalità di M, i.e., max| M|
Problema del matching di peso massimo MaxWeightedMatching (G(V,E),c,max):
Istanza: un grafo completo non orientato G(V,E) caratterizzato da un peso cij
per ogni arco (i,j)∈E
Soluzione: un matching M di G
matching
(di massima cardinalità)
Raffaele Pesenti
Obiettivo: massimo peso degli archi in M, i.e., maxΣe∈M ce
103
Raffaele Pesenti
104
Esempio formulazione PL
Problemi di matching
Commenti:
• Il problema MaxCardMatchingè riducibile a MaxWeightedMatching, basta
porre tutti i pesi degli archi uguale a 1.
• Il problema MaxWeightedMatching è riducibile banalmente (vedi esempio su
lucido successivo) ad un problema di assegnamento se il grafo è bipartito
completo, cosa sempre ottenibile introducendo eventualmente archi di costo
infinito. La soluzione ottima è un matching perfetto, cioè su ogni nodo incide
un arco del matching.
• Il problema MaxWeightedMatching è in P anche se il grafo non è bipartito,
viene tipicamente risolto attraverso algoritmi primali-duali.
c11= 8
Al problema MaxWeightedMatching (G(V,E),c,max)
su grafo bipartito in figura corrisponde:
c21= 5
max 8x11 + 7x12 + 4x13 + 5x21 + 2x22 + 9x23 +
+ 7x31 + 2x32 + 4x33
x11 + x12 + x13 = 1
x21 + x22 +x23 = 1
x31 + x32 +x33 = 1
x11 + x21 + x31 = 1
x12 + x22 + x32 = 1
x13 + x23 + x33 = 1
xij ∈{0,1} ∀ (i,j)
c13= 4
c12= 7
c22= 2
c32= 2
c31= 7
c23= 9
c33= 4
Dove xij =1 se (i,j) appartiene al matching, xij =0 altrimenti
Raffaele Pesenti
105
Raffaele Pesenti
Formulazione PL
Esempio formulazione in PL
Al problema MaxWeightedMatching (G(V,E),c,max) in
figura corrisponde:
Al problema MaxWeightedMatching (G(V,E),c,max) su grafo generico
corrisponde :
max Σe∈E ce xe
Σe∈δ(i) xe ≤ 1
Σe∈E(S) xe ≤ |S| /2
xe ∈{0,1} ∀ (i,j)
∀i∈V
∀S⊂V, |S| dispari
dove E(S) è l’insieme degli archi della sottorete indotta dal sottoinsieme dei
nodi S. Il secondo insieme di vincoli per |S| pari sono inutili in quanto
ottenibili per somma dei vincoli del primo gruppo.
Raffaele Pesenti
106
107
max x12 + 3x13 + 2x23 + 4x24 + 4x34
x12 + x13 ≤ 1
x12 + x23 + x24 ≤ 1
x13 + x23 + x34 ≤ 1
x24 + x34 ≤ 1
x12 + x13 +x23 ≤ 1
x12 + x24 ≤ 1
x13 + x34 ≤ 1
x23 + x24 +x34 ≤ 1
xij ∈{0,1} ∀ (i,j)
Raffaele Pesenti
2
1
1
S={1,2,3}
S={1,2,4}
S={1,3,4}
S={2,3,4}
4
4
2
3
3
4
108
Formulazione PL
Commenti:
• Il numero di vincoli è esponenziale.
• La condizione xij∈{0,1} può essere rilassata in xij≥ 0 ottenendo comunque un
problema equivalente a quello originale.
• Il problema può essere risolto attraverso l’uso di un oracolo di separazione.
Raffaele Pesenti
109