Università degli Studi di Roma
Tor Vergata
Corso di Laurea in
Ingegneria dei Modelli e dei Sistemi
Il problema della foresta di Steiner
STUDENTE
Marco Senatore
RELATORE
Gianpaolo Oriolo
 Generalizzazione del problema dell’albero di Steiner
Foresta di Steiner.
 Formulazione del problema in PLI.
• Rilassamento PL e duale.
 Algoritmo.
• Esempi.
• Analisi dell’algoritmo.
PROBLEMA:
Dati:
 un grafo non direzionato G = (V, E);
 una funzione costo a valori positivi c sugli archi ;
 una collezione di sottoinsiemi disgiunti di V: R1,.......,Rk.
Trovare:
 un sottografo F nel quale ogni coppia di vertici appartenenti
allo stesso insieme Ri è connessa;
Tale che:
 la somma dei costi degli archi di F sia minima.
OSS: se k=1
albero di Steiner.
V
R3
R1
R2
Definiamo la funzione r:
1
r (u, v)  
0
se (u, v)  Ri
altrimenti
Trovare F che contenga un path da u a v
per ogni coppia (u,v) con r(u,v)=1
La soluzione sarà una foresta
(ovvero un’unione di alberi disgiunti)
Introducendo f : 2V{0,1}
1
f (S )  
0
se  u  S , v  S : r (u, v)  1
altrimenti
e associando una variabile binaria xe ad ogni arco e, possiamo
formulare il problema nel seguente modo:
min
c x
eE
s.t.

e:e ( S )
e e
xe  f ( S ),
xe {0,1},
S V
e E
Il rilassamento lineare del problema è:
min
c x
eE
s.t.

e e
e:e ( S )
xe  f ( S ),
xe  0,
S V
e E
Il duale è:
max
 f (S ) y
S V
s.t.

S :e ( S )
S
ys  ce ,
yS  0,
e E
S V
Def : un arco è detto TIGHT
se il vincolo duale ad esso
corrispondente è soddisfatto
all’ uguaglianza
Def : si dice grado dell’insieme S il numero di archi selezionati
che appartengono al taglio (S,S).
CONDIZIONE PRIMALE :
e  E : xe  0 

S :e ( S )
ys  ce
Ogni arco selezionato
deve essere tight
CONDIZIONE DUALE RILASSATA :
S  V : yS  0 

e:e ( S )
xe  2 f ( S )
Algoritmo
2-approssimato
Data una soluzione primale x:
Def : un insieme S si dice insoddisfatto se:
• f (S)=1;
• xe  0e   (S ).
Def : un insieme S si dice attivo se:
• è insoddisfatto;
•  S’ S tale che S’ è insoddisfatto, ovvero S è
minimale
Prop. : un insieme S è attivo sse è una componente connessa della soluzione
corrente e f (S)=1.
L’algoritmo, iterativamente, migliora l’ammissibilità del primale e l’ottimalità
del duale fino ad ottenere una soluzione primale ammissibile.
1. Poniamo xe  0e  E, yS  0S  V ;
x non ammissibile, y ammissibile.
2. Aumentiamo in modo uniforme le ys relative agli insiemi attivi;
OSS: se la soluzione primale corrente è inammissibile   un insieme
attivo.
3. Quando un arco e diventa tight viene selezionato e le yS del vincolo duale
corrispondente ad e vengono ”congelate”;
4. Ripetere fino al raggiungimento di una soluzione ammissibile F;
5. (Pruning step)  e  F tale che F\{e} è ancora ammissibile, rimuovo e da F.
F’ = {e  F tale che F’\{e} è inammissibile}
.
u
6
16
.
s
.
v
20
.
a
12
9
.
V={a,b,s,t,u,v}
R1={s,t} R2={u,v}
6
19
b
12
.
t
OPT=45
r(s,t)=1
r(u,v)=1
2
2
1
.
1
u
a
16
s
v
20
6
.
.
6
12
.
9
.
6
Set attivi :{s},
{t},{v,b,t}
{u,a},{v}
:{t}, {u,s,a},
:{u,s,a},
{u},
{v}
{v,b}
3
6
b
ySS aumentate di 1206
19
.
12
8
6
ITERAZIONE 2:
1:
3:
4:
5:
2
t
6
8
9
(v,b)
tight, quindi
quindi lo
lo prendo
prendo
(u,a) tight,
(u,s)
(b,t)
(u,v)
.
u
6
16
.
s
.
v
20
a
.
.
Abbiamo una soluzione
ammissibile del primale
6
b
12
.
Pruning step
t
COSTO=54
 2 terminali
 5 nodi di Steiner
L’algoritmo aggiunge tutti gli archi di
costo 1 prima dell’arco di costo 3
. .
. .
. .
1
1
3
1
1
Costo(F) > 2OPT
1
Importanza del pruning step!
.
 F' ed y sono una coppia primale/duale ammissibile
Def : Con degF’(S) denotiamo il numero di archi di F’ che attraversano il taglio
(S,S).
Lemma : Si consideri un’iterazione dell’algoritmo, e sia C una componente
connessa della soluzione corrente. Se f (C )  0  deg F ' (C )  1.
Dim : Supponiamo degF’(C)=1.   ! e  F’ che attraversa il taglio (C,C). Poichè
e non è ridondante, c’è una coppia di vertici (u,v) tale che r(u,v)=1 ed e giace
sull’unico path u-v in F’. Questo path attraversa il taglio una sola volta, quindi un
vertice sta in C e l’altro in C. Allora, poichè r(u,v)=1, deduciamo che f(C)=1, il che
porta all’assurdo.

.
I VERTICI DI STEINER
SELEZIONATI DALLA
SOLUZIONE HANNO GRADO
ALMENO 2
Lemma:
c
e
eF '
Dim:
 2  yS
S V


ce     yS 

eF '
eF '  S :e ( S )

 deg
S V
F'


c

y
  S    deg F ' (S )  yS


e
eF '
S V  e ( S ) F '
 S V
( S )  yS  2  yS


    deg F ' ( S )   2  ( di S attivi)
 S attivi

S V

deg F ' ( S )
S attivi
(  di S attivi)
2
Equivale a dire che, fissata una iterazione k, il numero medio di archi della
soluzione FINALE F' che attraversano gli S attivi nell'iterazione k è al più 2 .
•Considero H=(V,F’) e le componenti attive di
F all’iterazione k;
H
•Contraggo le componenti attive in un singolo
nodo ed ottengo H’, elimando gli archi
introdotti fino all’iterazione k;
•I nodi s corrispondenti alle componenti
attive S, sono detti attivi, ed hanno grado pari
proprio a degF’(S); gli altri sono detti inattivi;
•H’ è un albero, quindi il grado medio dei suoi
nodi è  2;
•Per il lemma precedente i nodi inattivi hanno
grado almeno 2;
I nodi attivi hanno grado medio  2.
H’
 Abbiamo dato una formulazione primale/duale del
problema;
 Abbiamo fornito un algoritmo che ci restituisce una
coppia di soluzioni primale/duale ammissibili;
 Abbiamo dimostrato che la soluzione del primale vale
al più 2 volte la soluzione del duale;
 Questo ci ha permesso di dimostrare che l’algoritmo è
2-approssimato.
Def : Si dice taglio (S,S) di un grafo G=(V,E) una bipartizione dei suoi nodi in
due insiemi non vuoti S ed S
Def : Con δ(S) indicheremo l’insieme di archi di G che attraversano il taglio (S,S)
S
S
f(S)=0
f(S)=1
V
R3
R1
R2
Primale:
Duale:
min cT x
max bT y
Ax  b
s.t.
x0
s.t.
AT y  c
y0
Il valore di una qualsiasi soluzione duale ammissibile è un lower
bound al valore di una qualsiasi soluzione primale ammissibile
Teo 1: Se x ed y sono soluzioni ammissibili rispettivamente del primale e del
duale, allora cTx ≥ bTy
m
m
m

 n

c x   ci xi     Aij y j  xi    Aij xi  y j   b j y j  bT y
i 1
i 1  j i
j 1  i i
j 1


n
T
n
i, o xi  0 oppure
Condizione primale:
m
A y
j i
j , o y j  0 oppure
Condizione duale:
Condizione duale α-approssimata:
ij
j , o y j  0 oppure
n
A
i i
ij
j
 ci .
xi  b j .
n
A x
i i
ij
i
 bj .
Teo 2: Se x ed y sono soluzioni ammissibili rispettivamente del primale
e del duale, che soddisfano la condizione primale e la condizione duale
α-approssimata, allora x è una soluzione α-approssimata del primale
Dim :
cT x  ( AT y )T x  yT Ax   yT b
Ma per il Teo 1 yTb è  dell’ottimo
del primale, cTx*
cT x   cT x *
xPLI
xRL
yD
xRL
2
yD