Corso di Laurea in Corso di Laurea in Ingegneria dei Modelli e dei SistemiIngegneria dei Modelli e dei Sistemi

Il Il problema della foresta di Steinerproblema della foresta di Steiner

STUDENTE RELATORESTUDENTE RELATORE

Marco Senatore Gianpaolo OrioloMarco Senatore Gianpaolo Oriolo

Università degli Studi di Roma Università degli Studi di Roma Tor Vergata Tor Vergata

Generalizzazione del problema dell’albero di Steiner

Foresta di Steiner.

Formulazione del problema in PLI.

• Rilassamento PL e duale.

Algoritmo.

• Esempi.

• Analisi dell’algoritmo.

SOMMARIO

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.

OSS: se k=1 albero di Steiner.

LA FORESTA DI STEINER

Trovare:

Tale che:

un sottografo F nel quale ogni coppia di vertici appartenenti allo stesso insieme Ri è connessa;

la somma dei costi degli archi di F sia minima.

LA FORESTA DI STEINER

V

R1R2

R3

LA FORESTA DI STEINERDefiniamo la funzione r:

1 se ( , )( , )

0 altrimentiiu v R

r u v

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)

1 se , : ( , ) 1( )

0 altrimenti

u S v S r u vf S

: ( )

min

s.t. ( ),

{0,1},

e ee E

ee e S

e

c x

x f S S V

x e E

Introducendo f : 2V{0,1}

e associando una variabile binaria xe ad ogni arco e, possiamo formulare il problema nel seguente modo:

FORMULAZIONE PLI

: ( )

min

s.t. ( ),

0,

e ee E

ee e S

e

c x

x f S S V

x e E

: ( )

max ( )

s.t. ,

0,

SS V

s eS e S

S

f S y

y c e E

y S V

Il rilassamento lineare del problema è:

Il duale è:Def : un arco è detto TIGHT se il vincolo duale ad esso corrispondente è soddisfatto all’ uguaglianza

RILASSAMENTO E DUALE

CONDIZIONE PRIMALE/DUALE RILASSATADef : si dice grado dell’insieme S il numero di archi selezionati che appartengono al taglio (S,S).

CONDIZIONE PRIMALE :

: ( )

: 0e s eS e S

e E x y c

Ogni arco selezionato deve essere tight

CONDIZIONE DUALE RILASSATA :

: ( )

: 0 2 ( )S ee e S

S V y x f S

Algoritmo 2-approssimato

INSIEMI ATTIVI

Def : un insieme S si dice insoddisfatto se:

• f (S)=1;

• 0 ( ).ex e S

Prop. : un insieme S è attivo sse è una componente connessa della soluzione corrente e f (S)=1.

Data una soluzione primale x:

Def : un insieme S si dice attivo se:

• è insoddisfatto;

• S’ S tale che S’ è insoddisfatto, ovvero S è minimale

L’ALGORITMOL’algoritmo, iterativamente, migliora l’ammissibilità del primale e l’ottimalità del duale fino ad ottenere una soluzione primale ammissibile.

1. Poniamo 0 , 0 ;e Sx e E y S V

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}

x non ammissibile, y ammissibile.

20

16

6 6

199

12

12

u v

s t

ba

V={a,b,s,t,u,v} R1={s,t} R2={u,v}

r(s,t)=1 r(u,v)=1

OPT=45

. ..

..

.

ESEMPIO 1

20

16

6 6

199

12

12

6 6

66

2 2

2 1

.

. .

...

ITERAZIONE 1:

Set attivi :{s}, {t}, {u}, {v}

yS aumentate di 6

(u,a) tight, quindi lo prendo

ITERAZIONE 2:

Set attivi :{s}, {t}, {u,a}, {v}

yS aumentate di 0

(v,b) tight, quindi lo prendo

ITERAZIONE 3:

Set attivi :{s}, {t}, {u,a}, {v,b}

yS aumentate di 2

(u,s) tight, quindi lo prendo

ITERAZIONE 4:

Set attivi :{t}, {u,s,a}, {v,b}

yS aumentate di 1

(b,t) tight, quindi lo prendo

1

8

8

ITERAZIONE 5:

Set attivi :{u,s,a}, {v,b,t}

yS aumentate di 1

(u,v) tight, quindi lo prendo

3

9

u v

s t

a b

ESEMPIO 1

. .

. .

20

16

6 6

12

..Abbiamo una soluzione ammissibile del primale

COSTO=54

Pruning step

u

s

v

t

a b

ESEMPIO 1

.....

.

.1

3

11

1

1

2 terminali

5 nodi di Steiner

L’algoritmo aggiunge tutti gli archi di costo 1 prima dell’arco di costo 3

Costo(F) > 2OPT

Importanza del pruning step!

ESEMPIO 2

ANALISI DELL’ALGORITMO

Lemma : Si consideri un’iterazione dell’algoritmo, e sia C una componente connessa della soluzione corrente. 'Se ( ) 0 deg ( ) 1.Ff C C

Def : Con degF’(S) denotiamo il numero di archi di F’ che attraversano il taglio (S,S).

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

F' ed y sono una coppia primale/duale ammissibile

ANALISI DELL’ALGORITMO

Lemma:'

2e SS Ve F

c y

Dim:

' ' : ( )e S

e F e F S e S

c y

'

' ( ) '

deg ( )e S F Se F S V e S F S V

c y S y

'deg ( ) 2F S SS V S V

S y y

'

deg ( ) 2 ( di S attivi)FS attivi

S '

deg ( )2

( di S attivi)

FS attivi

S

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 .

ANALISI DELL’ALGORITMO

H

H’

•Considero H=(V,F’) e le componenti attive di F 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;

•Contraggo le componenti attive in un singolo nodo ed ottengo H’, elimando gli archi introdotti fino all’iterazione k;

•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.

CONCLUSIONE

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

V

R1R2

R3

f(S)=1 f(S)=0

LP DUALITY

min

s.t.

0

Tc x

Ax b

x

Primale:

max b

s.t.

y 0

T

T

y

A y c

Duale:

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

1 1 1 1

n n m m n mT T

i i ij j i ij i j j ji i j i j i i j

c x c x A y x A x y b y b y

LP DUALITY

, o y 0 oppure .n

j ij i ji i

j A x b

Condizione primale:

Condizione duale:

Condizione duale α-approssimata:

, o 0 oppure .m

i ij j ij i

i x A y c

, o y 0 oppure .n

j ij i ji i

j A x b

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

( )T T T T Tc x A y x y Ax y b Dim :

Ma per il Teo 1 yTb è dell’ottimo del primale, cTx*

*T Tc x c x

xPLI

xRL

yD

2RL

D

x

y