UNIVERSITA’ DEGLI STUDI DI SALERNO

FACOLTA’ DI SCIENZE MATEMATICHE FISICHE E NATURALI

Corso di laurea specialistica in informatica

A Branch & Bound algorithm for constrained

spanning trees

Relatori: Candidato: Prof. Raffaele Cerulli Ciro Sasso Dott. Carmine Cerrone 0521000701

Anno Accademico 2009/2010

2

…Alla mia famiglia che mi ha sempre sostenuto

durante questi lunghi sei anni…

Ringraziamenti

I miei ringraziamenti vanno:

Al Professor Raffaele Cerulli e al Dottor Carmine Cerrone, che mi

hanno seguito costantemente durante la stesura della tesi,

alla mia famiglia che mi ha sempre sostenuto economicamente e

moralmente durante l’intero arco dei miei studi,

a tutti i miei amici che mi sono sempre stati vicini anche nei momenti

di maggior difficoltà,

ed infine ai miei colleghi Alfredo Mondelli, Giovanni Esposito Alaia e

Luigi Ruocco compagni di 1000 avventure in questi 6 anni.

Grazie a tutti!!!

4

Indice

ABSTRACT.....................................................................................................................................6

1.INTRODUZIONE........................................................................................................................9

1.1.Definizione del problema e motivazioni ....................................................... 9 1.2.Formulazione matematica ...........................................................................11

2.BRANCH & BOUND.................................................................................................................15

2.1.Programmazione lineare intera e ottimizzazione combinatoria .................. 15 2.2.Metodi enumerativi e Branch-and-Bound................................................... 17

2.2.1.Generazione delle soluzioni: operazione di branch ............................. 18 2.2.2.Esplorazione effciente: operazione di bound ....................................... 20 2.2.3.Metodo del Branch and Bound (B&B): idea di base ........................... 24

2.3.Il metodo di Branch-and-Bound.................................................................. 24 2.3.1.Regole di Branching.............................................................................26 2.3.2.Calcolo del Bound................................................................................ 27 2.3.3.Regole di potatura o fathoming............................................................ 29 2.3.4.Regole di esplorazione dell'albero ....................................................... 30 2.3.5.Valutazione di soluzioni ammissibili ................................................... 31 2.3.6.Criteri di arresto ................................................................................... 32

3.ALGORITMO RISOLUTIVO:IDEA DI BASE................ ......................................................33

3.1.Selezione della radice.................................................................................. 34 3.2.Scelta del vicino per un nodo intermedio.................................................... 35 3.3.Lower Bound............................................................................................... 36

3.3.1.Stima nodi frontiere/foglie ................................................................... 37 3.3.2.Stima per eliminazione......................................................................... 38 3.3.3.Stima per eliminazione doppia............................................................. 40

4.OTTIMIZZAZIONI ..................................................................................................................41

4.1.Split del problema ....................................................................................... 41 4.1.1.Split basato sulle frontiere....................................................................42 4.1.2.Split basato sulle eliminazioni ............................................................. 43 4.1.3.Split in due componenti ....................................................................... 44

4.2.Upper Bound ............................................................................................... 46 4.2.1.Euristica 1............................................................................................. 47 4.2.2.Euristica “Suggeritore” ........................................................................ 49 4.2.3.Ricerca Locale...................................................................................... 51

4.3.Parental Semplification ............................................................................... 54 4.3.1.Basata su eliminazione......................................................................... 55 4.3.2.Basata su Inclusione............................................................................. 56

4.4.Ordinamento................................................................................................ 57

5.GESTIONE DELLA MEMORIA.............................................................................................59

6.STRUTTURA CODICE ............................................................................................................62

6.1.Class Diagram ............................................................................................. 62 6.2.Struttura del metoto “ottimo()” di Mbv ...................................................... 63

7.RISULTATI................................................................................................................................65

5

8.CONCLUSIONI E FUTURI SVILUPPI..................................................................................67

BIBLIOGRAFIA...........................................................................................................................69

Indice delle figure Figura 1:esempio di nodi branch........................................................................... 10 Figura 2:regione di ammibisibilità........................................................................ 16 Figura 3: Branch del problema.............................................................................. 19 Figura 4:esempio di albero decisionale................................................................. 21 Figura 5:esempio di bound per i sottoproblemi individuati .................................. 22 Figura 6:stima nodi frontiera/foglie ...................................................................... 38 Figura 7(A): grafo prima dell'eliminazione del nodo 9......................................... 39 Figura 8(B): grafo dopo l'eliminazione del nodo 9 ............................................... 39 Figura 9: esempio di stima per eliminazione doppia ............................................ 40 Figura 10: esempio di stima per eliminazione doppia.......................................... 40 Figura 11:split basato su frontiere......................................................................... 43 Figura 12:split basato su eliminazione.................................................................. 45 Figura 13:trasformazione delle componenti durante lo split................................. 46 Figura 14:grafo dato in input all'euristica ............................................................. 47 Figura 15:grafo dopo l'eliminazione dei nodi di grado 1 ...................................... 48 Figura 16:soluzione ammissibile individuata........................................................ 49 Figura 17:soluzione ammissibile presa in input dalla procedura.......................... 52 Figura 18:primo caso di miglioramento................................................................ 53 Figura 19:secondo caso di miglioramento ............................................................ 53 Figura 20: grafo di partenza dalla procedura ........................................................ 54 Figura 21:2 possibili soluzioni ammissibili .......................................................... 54 Figura 22:configurazione parenal semplification ad eliminazione ....................... 55 Figura 23:configurazione parental semplification per inclusione......................... 56 Figura 24:un esempio di grafo .............................................................................. 60 Figura 25:evidenziati 2 possibili cammini dalla radice al nodo 7......................... 60 Figura 26:class diagram ........................................................................................ 62 Figura 27:struttura metodo "ottimo" ..................................................................... 64 Figura 28(A):esempio split inutile ........................................................................ 67 Figura 29(B): esempio di split inutile ................................................................... 68

6

Abstract In questa tesi viene descritto un algoritmo esatto per la risoluzione di

una problematica sui grafi. Il problema è definito Minimum Branch

Vertex (MBV) e consiste in: dato un grafo in input G=(V,E), trovare

uno spanning tree T con il numero minimo di nodi branch (ossia di

nodi con grado maggiore di 2). Essendo il problema in questione NP-

HARD, l’algoritmo presentato risulta avere una complessità

esponenziale. Di seguito è descritta la struttura della tesi in maniera

riassuntiva per ciascun capitolo.

Capitolo 1: Il problema MBV è un problema che si presenta nella

costruzione delle reti ottiche. Affinché sia possibile garantire il multi

casting, in tali reti si necessita della presenza degli switch, ossia quei

nodi che smistano il segnale a più di un vicino. Ciascuno di essi ha un

suo costo, di conseguenza va minimizzato il numero di switch in una

rete. Ogni switch corrisponderà proprio ad ogni nodo branch della

soluzione identificata per un grafo iniziale.

Capitolo 2: In questo capitolo si presenta la tecnica utilizzata per la

risoluzione esatta del problema, il “Branch & Bound”. Tale tecnica

prevede di andare ad enumerare tutte le possibili soluzioni, prendendo

tra tutte quella migliore ai fini del problema. La bontà di un algoritmo

sviluppato in questa modalità dipende dalla qualità dai bound (lower e

upper) utilizzati. Questi vengono utilizzati per interrompere

l’esplorazione di determinati rami dell’albero decisionale che vengono

classificati come inutili, in quanto non potranno portare ad alcun

miglioramento della soluzione incombente.

Capitolo 3: L’algoritmo in questione ha una struttura ricorsiva e

prevede una costruzione della soluzione in maniera incrementale,

7

costruendone una nuova per ciascun ramo decisionale intrapreso.

L’idea base utilizzata per la risoluzione del problema del MBV

prevede i seguenti passi:

1. Selezionare un nodo radice dello spanning tree rendendolo il nodo

corrente.

2. Scegliere un suo vicino ed inserire in soluzione l’arco che li

connette rendendo il vicino, il nuovo nodo corrente.

3. Continuare cosi fino a che non saranno stati visitati tutti i nodi,

ottenendo una soluzione ammissibile. Ottenuta quest’ultima se ne

valuta il costo e si verifica se è più vantaggiosa rispetto all’ottimo

corrente, in caso positivo lo si aggiorna.

Capitolo 4: Affinché il problema possa trovare la soluzione in

maniera più rapida, sono state introdotte delle ottimizzazioni, tra cui:

• Split del problema in sotto problemi processati

indipendentemente.

• Utilizzo di euristiche per il calcolo di soluzioni ammissibili da

cui far iniziare l’elaborazione (in pratica un upperbound per il

problema).

• Varie politiche per evitare di visionare alcune strade dell’albero

decisionale.

Capitolo 5: In tale capitolo viene analizzato come viene gestita la

memoria dall’algoritmo. In realtà si è preferito una maggiore velocità

di esecuzione a scapito dello spreco di memoria. Questo perché, si

presuppone che essendo questo un software per l’ottimizzazione,

possa essere eseguito su macchine che non abbiamo particolari

restrizioni in termini di spazio di memorizzazione.

Capitolo 6: In questo capito si descrive come è stato strutturato il

codice.

8

Capitolo 7: Infine si termina evidenziando i risultati ottenuti e

comparandoli con quelli del risolutore matematico Cplex. Si è

mostrato che nei casi di un grafo in input poco denso o molto denso si

è riuscito a battere il software suddetto. Per i casi in cui ciò non è

avvenuto, si sono analizzati i problemi e sono state esposte nuove idee

per implementazioni future.

9

1.Introduzione Esistono molte varianti per il problema dello spanning tree, queste

vengono utilizzate per modellare i vari problemi che sorgono nelle reti

di comunicazione. Ad esempio, se nella rete fosse necessario

connettere uno specifico sottoinsieme di nodi (Steiner Tree Problem)

con dei link a cui è associata una qualche misura, si potrebbe essere

interessati al cercare sottografi omogenei nella rete, come nel

problema del Minimum Labelling Spanning Tree Problem. Nelle reti

ottiche ad esempio, può essere vantaggioso connettere i nodi in modo

che il numero di connessioni di ogni nodo sia limitato (Spanning Tree

with Minimum Number of Branch Nodes ).

Formalmente, dato un grafo connesso G, un vertice è considerato

branch se il suo grado è maggiore di due. Si considerino i problemi

derivanti, nel contesto delle reti ottiche :

• Trovare uno spanning tree di G con il minimo numero di

vertici branch.

• Trovare uno spanning tree di G in modo che la somma del

grado dei vertici branch sia minimizzata.

• Sia d la somma del grado dei vertici branch, sia b il numero di

vertici branch, trovare uno spanning tree di G tale che (d-(2*b))

sia minimizzata.

1.1.Definizione del problema e motivazioni

Un vertice in un grafo G è detto branch se e solo se il suo grado è

maggiore di due, ad esempio i vertici con etichetta B in figura sono

vertici branch.

10

Figura 1:esempio di nodi branch

Dato un grafo connesso G, possiamo definire il problema del minimo

numero di vertici branch(MBV) nel modo seguente:

• Trovare uno spanning tree di G con il minimo numero di vertici

branch.

Il problema MBV , ha implicazioni molto importanti nelle reti ottiche.

In questa nuova tipologia di reti di comunicazione, la divisione delle

onde sfruttando la tecnologia multiplexing, permette di propagare

differenti fasci di luce sulla stessa fibra ottica, anche se usano una

diversa lunghezza d’onda. Le tecnologie che fanno uso di multi

casting su reti ottiche, permettono di replicare il segnale ottico da un

nodo sorgente verso diversi nodi destinazione, utilizzando dei

dispositivi di rete, gli switch. Essi permettono di replicare il segnale,

suddividendo il fascio di luce. Una struttura ad albero del fascio di

luce, connette un nodo ad un sottoinsieme di nodi della rete,

permettendo quindi la comunicazione multicast.

11

I nodi di questo albero che hanno grado maggiore di due sono i

cosidetti vertici branch. Gli switch vengono utilizzati proprio su

questa tipologia di nodi. Dal momento che le reti ottiche hanno un

numero limitato di questi switch, è importante determinare il minimo

numero di switch da localizzare nella rete, per garantire le connessioni

multicast. Questa tipologia di problemi è stata studiata da Gargano et

al. in [1] . Lo studio ha portato a dimostrare che questo problema è

NP-Completo. Inoltre, è introdotto un problema correlato: trovare uno

spanning tree di un grafo in modo che la somma del grado dei vertici

branch nell’albero sia minimizzato. La definizione del Minimum

Degree Sum Problem (MDS) è :

• Trovare uno spanning tree di G in modo che la somma del grado

dei vertici branch sia minimizzata.

Questo problema è stato introdotto da Cerulli et al. in [2]. Le ragioni

dell’introduzione di questo nuovo problema sono motivate dalla

necessità di creare un modello più adatto al problema reale delle reti

ottiche, infatti, molti devices possono solo duplicare il fascio di luce, e

quindi il numero di devices da localizzare su un nodo branch per

replicare il fascio di luce, è direttamente correlato al numero di archi

incidenti sul nodo. In un vertice branch il numero di switch ottici

necessari per duplicare il segnale è strettamente correlato al grado dei

vertici ed in particolare, se il grado del vertice v è uguale ad x,

abbiamo bisogno di x-2 split.

1.2.Formulazione matematica

Si consideri un grafo non direzionato G = (V,E), dove V denota

l’insieme di n vertici ed E l’insieme di m archi. Consideriamo la

12

versione orientata del grafo dove due archi (u,v) e (v,u) sono entrambi

associati all’arco (u,v) ∈ E. Denotiamo con E’ questo nuovo set di

archi. Il set di variabili per il modello sono le seguenti:

• La variabile binaria ex , per ogni e∈ E che assume valore 1 se

l’arco è selezionato e 0 altrimenti;

• La variabile binaria vy , per ogni v∈ V che assume valore 1 se v è

un vertice branch e 0 altrimenti;

Denotiamo con A(v) l’insieme di vertici incidenti su v e con vδ il sua

taglia, es. |A(v)| =vδ . Denotiamo con )( vA + e )( vA −

rispettivamente l’insieme degli archi uscenti ed entranti del nodo v in

E’. Uno spanning tree T di G può essere trovato inviando un’unita di

flusso da una sorgente s∈ V ad ogni altro vertice v∈ V \ {s} del grafo.

Introduciamo entrambe le variabili, uvx per ogni (u,v) ∈ E’ che

assume valore 1 se l’arco è selezionato o 0 altrimenti e la variabile di

flusso uvf per ogni (u,v) ∈ E’ rappresentante l’unità di flusso che va

da u a v. La formulazione di flusso single commodity (SC) per l’

MBV è la seguente:

13

La funzione obiettivo (3.3.1) è la minimizzazione dei vertici branch

totali. Il vincolo (3.3.2) assicura che ogni vertice branch nello

spanning tree abbia esattamente un arco entrante. Le equazioni (3.3.3)

e (3.3.4) bilanciano il flusso su ogni vertice ed assicurano la

connessione di ogni soluzione ammissibile. Il vincolo (3.3.5) esprime

il collegamento tra le variabili di flusso f con le variabili binarie x. Il

vincolo (3.3.6) assicura che ogni variabile vy sia uguale ad 1, ogni

volta che v ha più di due archi incidenti nello spanning tree ottimo.

Invece la formulazione matematica per MDS richiede variabili

decisionali intere addizionali, per il conteggio del grado dei vertici

della soluzione:

14

Il modello matematico per MDS richiede di minimizzare la seguen

funzione obiettivo:

soggetta ai vincoli (3.3.2) – (3.3.9) e ai vincoli addizionali:

15

2.Branch & Bound

Per la risoluzione del problema si è pensato ad una tecnica di

risoluzione esatta ossia quella del Branch & Bound.

2.1.Programmazione lineare intera e ottimizzazione

combinatoria

Consideriamo un problema di Programmazione Lineare Intera (PLI)

nella forma:

min / max cT x

s.t. Ax = b nx +∈ Ζ

e chiamiamo

P = { nNx +∈ : Ax = b}

il poliedro delle soluzioni ammissibili ignorando il vincolo di

interezza delle variabili e

X = P ∩ n+Ζ

l'insieme delle soluzioni ammissibili, cioè intere (vedi figura che

segue).

16

Figura 2:regione di ammibisibilità

Il nostro obiettivo è quello di trovare una soluzione del PLI, ossia x*ε

X : cT x*≤ cT x, Xx∈∀ .

Si osservi, come è evidente dalla stessa Figura, che il problema non

può essere risolto con metodi per programmazione lineare a variabili

reali (ad esempio, il metodo del simplesso): in generale, il vertice

ottimale non è a coordinate intere (dipende dal poliedro ammissibile e

dalla funzione obiettivo) e non sempre l'approssimazione intera

ottenuta per arrotondamento è ottima e/o ammissibile!

Uno dei metodi risolutivi per problemi di PLI è il metodo del Branch-

and-Bound, che è descritto nel prossimo paragrafo. Tale metodo è un

metodo generale, applicabile ai problemi di ottimizzazione

combinatoria. In effetti, i problemi di PLI possono essere visti come

casi particolari di problemi di ottimizzazione combinatoria.

Un problema di ottimizzazione combinatoria è definito come:

min / max cT x

s.t. Xx∈

17

dove X è un insieme FINITO di punti e f(x) è una generica funzione

obiettivo.

Per alcuni problemi di ottimizzazione combinatoria esistono algoritmi

efficienti (problemi nella classe P, come ad esempio il problema del

cammino minimo), mentre per gli altri si deve considerare un

algoritmo risolutivo esatto di complessità esponenziale, oppure, se è

sufficiente una “buona” soluzione e non forzatamente quella ottima, si

può considerare un algoritmo efficiente ma approssimato (algoritmi

euristici e meta-euristici).

2.2.Metodi enumerativi e Branch-and-Bound

Il metodo esatto per problemi di ottimizzazione combinatoria che

consideriamo si basa su uno schema enumerativo che sfrutta la

finitezza dello spazio delle soluzioni ammissibili.

Lo schema è detto Algoritmo universale per ottimizzazione

combinatoria:

1. si generano tutte le possibili soluzioni x

2. si verifica l'ammissibilità della soluzione Xx∈

3. si valuta f(x)

4. scelgo la x ammissibile cui corrisponde la migliore f(x).

Ovviamente, lo schema è molto semplice ma sorge di due evidenti

problemi. Il primo, è che la valutazione di f(x) potrebbe non essere

banale (ad es. potrebbe essere necessaria una simulazione per valutare

la bontà di una soluzione). Il secondo, più generale, è che la

cardinalità di X potrebbe essere molto elevata. In particolare, la

seconda osservazione pone due questioni:

1. come generare lo spazio delle soluzioni (ammissibili)?

18

2. come esplorare efficientemente lo spazio delle soluzioni?

L'algoritmo del branch-and-bound implementa lo schema

dell'enumerazione sopra visto cercando di dare una risposta a queste

esigenze.

2.2.1.Generazione delle soluzioni: operazione di branch

Per capire come generare le soluzioni ammissibili, osserviamo che:

Dato un problema di ottimizzazione combinatoria

z = min / max {cT x s.t. Xx∈ }

e data una suddivisione della regione ammissibile X in insiemi

X1,X2,…,Xn : XXn

ii =

=U

1

, sia z(k) = max / min{f(x) : x ε Xk}.

Allora la soluzione del problema z =max / mink=1,..,n z(k) .

Possiamo quindi applicare il principio divide et impera: si suddivide X

in sottoinsiemi più piccoli, e si risolve il problema su ogni sotto-

insieme. Questo viene fatto ricorsivamente, dividendo a loro volta le

regioni ammissibili dei sotto-problemi in sottoinsiemi. Se tale

ricorsione venisse svolta completamente, alla fine enumereremmo

tutte le possibili soluzioni ammissibili del problema. La divisione

ricorsiva dell'insieme delle soluzioni del problema di partenza

(insieme X) da luogo ad un albero delle soluzioni ammissibili, come

rappresentato in Figura 2.

19

Figura 3: Branch del problema

Sia P0 il problema di ottimizzazione combinatoria in esame cui

corrisponde l'insieme delle soluzioni E0 = X. E0 è la radice dell'albero

e, in generale, Ei è l'insieme delle soluzioni associate al nodo i.

L'operazione di suddivisione di un nodo Ei da luogo a dei nodi figli .

Tale suddivisione deve garantire che:

Uj

ji EE = ,con j è figlio di i

cioè, le soluzioni presenti nel nodo padre devono essere presenti in

(almeno) uno dei suoi figli. In altre parole, nello sviluppo dell'albero si

deve garantire di non poter perdere soluzioni (altrimenti l'osservazione

sopra riportata non sarebbe valida). Una caratteristica auspicabile, ma

non necessaria, della suddivisione di un nodo Ei è la disgiunzione dei

sottoinsiemi figli (la suddivisione sarebbe in questo caso una

partizione in senso insiemistico):

=∩ ji EE , kj ,∀ figlio di i

20

L'operazione di suddivisione si fermerebbe nel momento in cui ogni

nodo contiene una sola soluzione. Pertanto, se Ef è un nodo foglia, si

ha |Ef | = 1.

La fase di costruzione di nodi figli per partizione di un nodo padre è

detta BRANCH se: un insieme di livello h viene suddiviso in t insiemi

di livello h + 1.

Esempio : Si consideri un problema di ottimizzazione combinatoria

con n variabili binarie xi ε {0,1}, i=1…n.

In questo caso, dato un problema Pi e il corrispondente insieme di

soluzioni ammissibili Ei, possiamo facilmente ottenere due sotto-

problemi e due sottoinsiemi di Ei fissando una delle variabili binarie a

0 per un sotto-problema e a 1 per l'altro sotto-problema.

Utilizzando questa regola di branch binario (ogni nodo è suddiviso in

due nodi figli) otterremmo l'albero delle soluzioni in Figura 4.

Ad ogni livello viene fissato a 0 o a 1 il valore di una delle variabili.

Un nodo di livello h quindi, contiene tutte le soluzioni ammissibili con

le variabili x1,…,xh fissate ad un preciso valore e, pertanto, tutti i nodi

sono disgiunti. Le foglie si trovano pertanto al livello n, dove tutte le

variabili sono state fissate: ogni foglia rappresenta una delle possibili

stringhe binarie di n bit e, quindi, una (ed una sola) possibile soluzione

del problema in questione. Si noti come il numero di foglie è 2n e il

numero di livelli è n + 1 (incluso il livello 0 della radice).

2.2.2.Esplorazione effciente: operazione di bound

In generale, il numero di foglie ottenute con un'operazione di branch è

esponenziale.L'esplosione completa di un albero di soluzioni,

21

corrispondente all'enumerazione di tutte le soluzioni in X è pertanto

non praticabile come metodo risolutivo. Cerchiamo quindi un metodo

che ci permetta di esplorare solo aree “buone” della regione

ammissibile, cercando di escludere a priori che la soluzione ottima del

problema si possa trovare in altre aree. Per fare questo, consideriamo,

per ogni nodo dell'albero, un BOUND, ossia una valutazione

ottimistica (non peggiore) del valore che la funzione obiettivo può

assumere in ciascuna delle soluzioni rappresentate dal nodo stesso.

Figura 4:esempio di albero decisionale

Ad esempio, consideriamo un problema di minimizzazione con

variabili binarie e supponiamo di disporre di una soluzione

ammissibile di valore 10. Supponiamo di associare, all'insieme delle

soluzioni ammissibili per il problema di partenza, il nodo E0 e di

sviluppare il primo livello dell'albero di branching, fissando la

22

variabile x1 a 0 e a 1 e ottenendo due nodi figli E1 ed E2 (vedi Figura

4).

Figura 5:esempio di bound per i sottoproblemi individuati

Chiamiamo z(1) il valore ottimo della funzione obiettivo nel

sottoinsieme E1 e z(2) il valore ottimo della funzione obiettivo nel

sottoinsieme E2. Ricordiamo che, come precedentemente osservato, il

valore ottimo della funzione obiettivo del problema in esame

z=min{z(1),z(2)}

Supponiamo ora di riuscire a stabilire, con qualche ragionamento e

senza considerare ad una ad una le soluzioni, che il valore delle

soluzioni ammissibili per il problema, una volta fissato a 0 il valore di

x1 non possa essere minore di 9. In altre parole, il valore della

funzione obiettivo in corrispondenza di ciascuna delle soluzioni

rappresentate dal nodo E1 è sicuramente non inferiore a 9.

9 rappresenta quindi una valutazione ottimistica della funzione

obiettivo per il sottoinsieme E1, un limite inferiore (lower bound) sotto

il quale il valore della funzione obiettivo non può scendere, se

consideriamo solo soluzioni in E1: cioè z(1) ≥ 9.

Analogamente, supponiamo di disporre di un lower bound per E2 e sia

tale bound pari a 11: nessuna della soluzioni con x1 = 1 (soluzioni in

23

E1) ha un valore della funzione obiettivo più basso di 11: cioè z(1) ≥11.

Ora, secondo la nostra prima osservazione, z=min{z(1),z(2)}.

Inoltre, utilizzando l'informazione sulla soluzione ammissibile a

disposizione, z ≤ 10 e, pertanto z(2) ≥ 11 ≥ 10, cioè, non è possibile

trovare una soluzione con valore migliore di 10 tra le soluzioni nel

nodo E2. Pertanto, E2 non contiene sicuramente la soluzione ottima ed

è inutile sviluppare ed esplorare il sotto-albero con radice E2.

Lo stesso ragionamento non vale per il nodo E1: una delle soluzioni in

questo nodo potrebbe avere valore inferiore a 10 e, pertanto, tale nodo

potrebbe contenere la soluzione ottima.

In generale, se è nota una soluzione ammissibile x’ di valore f(x’) = f’,

la disponibilità di un bound associato ai nodi dell'albero di branch ci

permette di “potare” (non sviluppare) sotto-alberi che sicuramente non

contengono la soluzione ottima, cioè i sotto-alberi radicati in un nodo

con bound non migliore di f’.

Osserviamo che, anche se non abbiamo esplicitato tutti i nodi foglia

del sotto-albero di E2, siamo comunque in grado di stabilire che il

valore di ciascuno di essi non è migliore di 11 e, grazie alla soluzione

ammissibile, tale informazione è suffciente per escluderli come

soluzioni ottime: è come se avessimo esplorato tutto il sotto-albero in

maniera implicita.

Attraverso l'operazione di bound è quindi possibile effettuare una

enumerazione implicita di tutte le soluzioni di un problema di

ottimizzazione combinatoria.

24

2.2.3.Metodo del Branch and Bound (B&B): idea di base

Dalle osservazioni precedenti, è possible definire il metodo del Branch

and Bound (B&B) per la soluzione di problemi di ottimizzazione

combinatoria. Si tratta di un metodo che enumera in modo esplicito o

implicito tutte le soluzioni del problema, basandosi sui seguenti

elementi:

• operazione di branch: costruzione dell'albero delle soluzioni

ammissibili;

• disponibilità di una soluzione ammissibile di valore f’;

• operazione di bound: valutazione ottimistica della funzione

obiettivo per le soluzioni rappresentate da ciascun nodo (bound),

per evitare lo sviluppo completo di sotto-alberi (enumerazione

implicita delle soluzioni rappresentate dai nodi con bound non

migliore di f’).

2.3.Il metodo di Branch-and-Bound

Il metodo del Branch-and-Bound può essere schematizzato come

segue. Dato un problema di ottimizzazione combinatoria z(k) = max /

min{f(x) : x ∈ X} , sia:

• P0: problema di ottimizzazione iniziale;

• L: lista dei nodi aperti. Ogni nodo è una coppia (Pi;Bi), dove Pi è il

sotto-problema Bi è il relativo bound;

• z : valore della migliore soluzione ammissibile.

• x : migliore soluzione ammissibile corrente

25

Metodo di Branch-and-Bound

Inizializzazione: Esegui una stima ottimistica B0 della funzione

obiettivo e poni L = f(P0;B0) , x = , z = +∞

(min)[- ∞ (max)];

Criterio di Stop: Se L = allora STOP: x è la soluzione ottima. Se

superati limiti di tempo, nodi esplorati, nodi aperti

|L| etc. STOP: x è una soluzione (non

necessariamente ottima);

Selezione nodo: Seleziona (Pi;Bi) ∈ L per effettuare il branch;

Branching: Dividi Pi in t sotto-problemi Pij , j = 1,…,t

( ij j PPU = )

Bounding: Valuta una stima ottimistica Bij (in corrispondenza

di una soluzione non necessariamente ammissibile

Rijx ) per ciascun sotto-problema Pij;

Fathoming: Se Pij non è ammissibile, vai a 1.

Se Bij non è migliore di z ammissibile, vai a 1.

Se Rijx è ammissibile (e migliore di z ), poni

ijBz ← , Rijxx ← ;

elimina da L tutti i nodi k con Lk non migliore di ;

vai a 1.Altrimenti, aggiungi (Pij ;Bij) a L e vai a 1.

26

Quello sopra esposto è uno schema di principio per la soluzione di

problemi di ottimizzazione combinatoria. Per implementare un

algoritmo B&B per uno specifico problema, bisogna determinare i

seguenti elementi essenziali:

• Regole di Branching: come costruire l'albero delle soluzioni.

• Calcolo del Bound: come valutare i nodi.

• Regole di Fathoming: come chiudere e dichiarare sondati

(fathomed) i nodi.

• Regole di esplorazione dell'albero: definire le priorità di visita dei

nodi aperti.

• Come valutare una o più soluzioni ammissibili (soluzioni da

confrontare con i bound per chiudere nodi).

• Criteri di stop: condizioni di terminazione dell'algoritmo.

2.3.1.Regole di Branching

Le regole di branching permettono di costruire un albero di soluzioni

ammissibili e devono rispecchiare il principio del divide et impera: si

passa da un problema P con soluzioni E a una partizione in sotto-

problemi Pi con soluzioni U i i EE = (non si perdono soluzioni

ammissibili). Inoltre, per motivi di effcienza computazionale,

conviene avere =∩ ji EE ,in modo da evitare duplicazioni di

soluzioni in porzioni diverse dell'albero delle soluzioni.

Osserviamo che:

• la condizione U i i EE = assicura che la soluzione ottima si trovi

in almeno uno dei nodi figli;

27

• gli Ei sono sempre più piccoli: ciascun nodo Ei eredita

ricorsivamente le condizioni restrittive dei genitori (i

corrispondenti problemi Pi sono sempre più vincolati).

• i Pi sono sempre più semplici: al limite, in un nodo foglia f, Ef

contiene una sola soluzione e la soluzione di Pf è immediata.

• Ovviamente, esistono vari modi per effettuare il branch di un nodo

e bisogna, di volta

• in volta, stabilire la strategia di branching più adatta al problema.

Bisogna, ad esempio, stabilire:

• quanti nodi figli generare: ad esempio, si può effettuare un

branching binario (2 figli per nodo) o t-ario (t figli per nodo);

• come effettuare il branching: in generale, ciascuno dei sotto-

insiemi da associare ai nodi figli si ottiene ponendo dei limiti alla

variazione di una o più variabili decisionali e, per ciascun nodo,

bisogna decidere quali variabili considerare e che limiti imporre;

• etc. etc. etc.

2.3.2.Calcolo del Bound

Dato un problema Pi ed il relativo Ei, è necessario, ad ogni nodo,

calcolare una stima ottimistica della migliore soluzione in Ei. Tale

stima rappresenta un limite al miglior valore ottenibile se si

sviluppasse il sotto-albero con radice Ei. Osserviamo che, per

problemi di min, la valutazione ottimistica corrisponde ad un valore

sotto il quale siamo sicuri di non scendere, ossia si tratta di un limite

inferiore, un lower bound (LB) per il nodo Ei (LBi ≤ soluzione ottima

in Ei). Per problemi di max, serve invece stabilire un limite superiore

che siamo sicuri di non poter superare, un upper bound (UB) per

28

ciascun nodo Ei (UBi ¸ soluzione ottima in Ei). Ribadiamo che, per

ottenere il bound di un nodo, non ha senso considerare tutte le

soluzioni rappresentate dal nodo stesso (a meno che, trovandosi a

livelli molto profondi dell'albero di ricerca, le soluzioni non siano

veramente poche). In generale, quindi, è necessario determinare un

metodo per calcolare il bound che utilizzi solo una descrizione

implicita delle caratteristiche delle soluzioni rappresentate da un nodo.

Nello stabilire il metodo bisogna valutare il compromesso tra la

facilità di calcolo (effcienza computazionale) e la qualità (effcacia) del

bound che si ottiene. Per quanto riguarda l'effcienza computazionale,

osserviamo che il bound viene calcolato ad ogni nodo e, come è facile

immaginare, il numero di nodi da valutare potrebbe essere molto

elevato (esponenziale nei casi peggiori). Pertanto il metodo di

valutazione del bound deve garantire dei tempi di calcolo molto

rapidi, altrimenti il metodo del B&B nel suo complesso diventa

ineffciente.

Per quanto riguarda invece la qualità del bound, il limite ottenuto deve

essere il più stringente possibile, sempre garantendo che il bound sia

una valutazione ottimistica del nodo. In questo modo, una volta

disponibile una soluzione ammissibile per il problema, si può

permettere di potare un maggior numero di nodi. Si fa notare che, per

problemi di min, il bound deve essere il più alto possibile (ma sempre

minore o uguale al valore ottimo per quel nodo), mentre, per problemi

di max, il più basso possibile (ma sempre al di sopra del valore ottimo

per quel nodo).

29

2.3.3.Regole di potatura o fathoming

La disponibilità di un bound (da confrontare con il valore di una

soluzione ammissibile) rende possibile dichiarare esplorati in modo

implicito (fathomed) i nodi che sicuramente non contengono una

soluzione ottima. Questi nodi non sono ulteriormente

sviluppati(vengono cioè chiusi ) e il relativo sotto-albero viene potato.

Un nodo Ei con bound Bi viene chiuso (e quindi esplorato

implicitamente) se si verifica (almeno) una delle seguenti

condizioni:

• N.M. Assenza di soluzione migliorante: la valutazione

ottimistica Bi è NON MIGLIORE di una soluzione ammissibile

nota.

• S.A. Soluzione ammissibile: la valutazione ottimistica Bi è in

relazione ad una soluzione ammissibile. Nel nodo Ei non si

possono trovare soluzioni ammissibili migliori di quella che ho

calcolato, e quindi non ha senso continuare l'esplorazione del

sotto-albero.

• N.A. Problema non ammissibile: il problema Pi corrispondente

al nodo in esame non ammette soluzioni (Ei = ). L'insieme

delle condizioni che determinano il problema Pi si ottiene

considerando tutte le condizioni del problema originario più le

condizioni che hanno generato i progenitori (problemi sul

percorso dal nodo radice al nodi in esame ). Tali condizioni

potrebbero entrare in conflitto tra loro.

Nel caso S.A.: il valore del bound Bi coincide con una soluzione

ammissibile ed è pertanto il valore di una soluzione ammissibile. Si

procede quindi a confrontare il bound ottenuto, con il valore della

30

migliore soluzione ammissibile a disposizione e, se Bi è migliore, si

aggiorna la soluzione ammissibile corrente e si procede a verificare la

condizione N.M. sugli altri nodi ancora da esplorare. E’ possibile

infatti che il valore migliorato della soluzione ammissibile sia non

peggiore dei bound calcolati in precedenza, permettendo così la

chiusura di alcuni nodi.

2.3.4.Regole di esplorazione dell'albero

Tra i diversi nodi ancora aperti, bisogna decidere su quale nodo

effettuare il branching. La scelta influenza il numero di nodi

complessivamente aperti, e quindi l'efficienza del metodo. Possono

essere adottate diverse strategie di esplorazione che permettono di

stabilire quale sia il prossimo nodo per il branch:

• Depth First : il nodo di livello maggiore (più profondo). Il metodo

è semplice da implementare, permette di ottenere presto delle

soluzioni ammissibili (ci si avvicina più rapidamente alle foglie) e

limita la memoria necessaria per memorizzare l'albero delle

soluzioni, visto che si tendono a chiudere molti nodi per

ammissibilità e rimangono pochi nodi contemporaneamente aperti.

Per contro, presenta il rischio di esplorare completamente sotto-

alberi con soluzioni scadenti;

• Best Bound First o Best node: si sceglie il nodo più promettente,

ossia il nodo conil bound migliore (lower bound più basso, per

problemi di minimo, o upper bound più alto, per problemi di

massimo). Tipicamente, tale strategia permette di limitare il

numero di nodi visitati esplicitamente e tende pertanto a essere più

effciente. Percontro, l'esplorazione tende a rimanere a livelli poco

profondi, dove i problemi sono meno vincolati e, di conseguenza, i

31

bound sono più promettenti. Di conseguenza, difficilmente si

ottengono presto soluzioni ammissibili che migliorino quella

corrente per applicare efficacemente le regole di fathoming, e,

pertanto è maggiore la richiesta di memoria per i nodi aperti

contemporaneamente.

• Regole miste: i nodi vengono scelti alternando i diversi criteri, per

evitarne gli svantaggi. Ad esempio, all'inizio si applica una

strategia Depth First e, quando si ha una “buona” soluzione

ammissibile, si passa alla strategia Best Bound First.

2.3.5.Valutazione di soluzioni ammissibili

Per applicare efficacemente le regole di fathoming, è necessario

disporre di soluzioni ammissibili di buona qualità. Nella

predisposizione di un algoritmo di Branch-and-Bound, bisogna quindi

stabilire come e quando calcolare soluzioni ammissibili. Tra le varie

possibilità, citiamo:

• aspettare semplicemente che l'enumerazione generi un nodo foglia

ammissibile;

• implementare un algoritmo euristico che valuti una buona

soluzione all'inizio, prima dell'esplorazione;

• sfruttare, con frequenza da valutare, l'informazione raccolta

durante l'esplorazione dell'albero per costruire soluzioni

ammissibili sempre migliori.

• In ogni caso, bisogna sempre valutare il compromesso tra la qualità

della soluzione ammissibile corrente e lo sforzo computazionale

per ottenerla.

32

2.3.6.Criteri di arresto

Il metodo del Branch-and-Bound si arresta quando tutti i nodi sono

dichiarati fathomed. In questo caso, la soluzione ammissibile corrente

corrisponde ad una soluzione ottima.Possono anche essere adottati

criteri relativi a limiti computazionali, come ad esempio raggiunti

limiti di tempo di calcolo o di memoria, ma non è garantito che

l'eventuale soluzione ammissibile corrente sia ottima.

33

3.Algoritmo risolutivo:idea di base

L’algoritmo sviluppato appartiene alla famiglia degli algoritmi Branch

& Bound . Tale famiglia prevede che l’algoritmo valuti tutte le

possibili soluzioni per determinare quella ottima. La bontà di in

algoritmo appartenente a tale famiglia si stabilisce sulla base delle

stime adottate per far si che determinate strade dell’albero decisionale

possano essere escluse a priori dalla ricerca, in modo da risparmiare

cicli computazionali inutili ai fini del problema.

L’algoritmo in questione ha una struttura ricorsiva e prevede una

costruzione della soluzione in maniera incrementale, costruendo per

ciascun ramo decisionale intrapreso, una nuova soluzione.

L’idea base utilizzata per la risoluzione del problema del MBV

prevede i seguenti passi:

1. Selezionare un nodo radice dello spanning tree rendendolo il nodo

corrente.

2. Scegliere un suo vicino ed inserire in soluzione l’arco che li

connette rendendo il vicino, il nuovo nodo corrente.

3. Continuare cosi fino a che non saranno stati visitati tutti i nodi,

ottenendo una soluzione ammissibile. Ottenuta quest’ultima se ne

valuta il costo e si verifica se è più vantaggiosa rispetto all’ottimo

corrente, in caso positivo lo si aggiorna.

Prima di scendere nel dettaglio di ciascuno dei punti elencati è

doveroso descrivere come l’algoritmo considera i nodi del grafo

durante la sua esecuzione,a tal proposito vengono elencate le tre

categorie utilizzate:

34

• ATTIVI: sono considerati appartenenti a tale categoria quei nodi

per quali non è stata presa ancora alcuna decisione(o meglio quei

nodi che ancora non sono stati processati).Inizialmente sono tutti

attivi.

• FRONTIERA:sono considerati appartenenti a tale categoria quei

nodi per i quali l’algoritmo deve prendere una decisione

correntemente(o più precisamente, quei nodi per i quali l’algoritmo

deve scegliere il vicino su cui spostarsi).

• INATTIVI: sono considerati appartenenti a tale categoria quei nodi

già processati.

L’algoritmo può essere visto separato in due macro blocchi: uno

relativo alle decisioni prese sul nodo radice ed un altro relativo ai nodi

restanti, ciò è dovuto al problema che si sta risolvendo. L’obiettivo è

quello di minimizzare il numero dei nodi branch, di conseguenza

essendo la radice un nodo che non prevede archi entranti, ci mette

nella posizione di poter prendere decisioni differenti rispetto agli altri

nodi.

Di seguito vengono analizzati nel dettaglio ciascuno dei 3 punti

suddetti:

3.1.Selezione della radice

La scelta della radice viene effettuata scegliendo tra i nodi del grafo

iniziale, un nodo di grado 2. Questa scelta è giustificata dal fatto che

la radice non avrà archi entranti e ciò permette di inserire in soluzione

2 suoi vicini anziché uno, senza far aumentare il costo della soluzione

finale. Questo modo di procedere si differenzia dal modo di procedere

sul resto del grafo, in quanto, piuttosto che valutare ogni possibile

35

strada verso un vicino della radice, si valuterà ogni possibile strada

dalla radice verso ogni possibile coppia di vicini. Ciò potrebbe portare

ad una crescita in larghezza dell’albero decisionale dell’algoritmo e di

conseguenza dei tempi di esecuzione. Diventa quindi chiaro il motivo

per cui si preferisce selezionare un nodo che abbia grado due come

radice dell’albero ricoprente, se questo non è presente si sceglie il tra i

nodi di grado maggiore di 2 ,quello di grado minimo.

Funzionamento macro-blocco 1:

• Una volta selezionato la radice la si rende INATTIVA.

• A turno,per ogni coppia di vicini, li si rende FRONTIERA

inserendo in soluzione gli archi che li connettono alla radice.

o Si richiama macro-blocco 2 sul grafo residuo.

• Infine si scelgono gli archi dalla radice verso tutti i suoi vicini (che

nel caso di radice con grado maggiore di 2 comporta un incremento

del costo della soluzione).

o Si richiama macro-blocco 2 sul grafo residuo.

3.2.Scelta del vicino per un nodo intermedio

A questo punto parte il secondo macro blocco dell’algoritmo in

questione, che esegue semplicemente quanto detto prima:

Funzionamento macro-blocco 2:

• Si estrae un nodo frontiera, lo si rende il nuovo nodo corrente e lo

si setta come INATTIVO.

36

• A turno, per ogni suo vicino, se ne sceglie uno e lo si rende

FRONTIERA inserendo in soluzione l’arco che lo connette con il

nodo corrente.

o Si richiama ricorsivamente il macro-blocco 2 sul grafo

residuo.

• Infine si scelgono gli archi dal nodo corrente verso tutti i suoi

vicini (che nel caso di nodo con grado maggiore di 2 comporta un

incremento del costo della soluzione).

o Si richiama ricorsivamente il macro-blocco 2 sul grafo

residuo.

3.3.Lower Bound

Fondamentalmente non è detto che l’algoritmo arrivi ad ottenere una

nuova soluzione ogni volta, in quanto se durante l’esplorazione di un

ramo decisionale ci si rende conto che la soluzione attuale ha

raggiunto un costo pari a quello della soluzione ottima corrente,

l’algoritmo termina quell’esplorazione in quanto nel migliore dei casi

si potrà ottenere una soluzione che non è migliore di quella già

conosciuta.

In realtà per far si che l’algoritmo possa essere agevolato nell’

individuazione dei rami decisionali che possono esser terminati

anticipatamente o addirittura essere saltati a priori, vengono utilizzate

delle stime (anche definite Lower Bound). Queste ultime non sono

altro che semplici procedure che, eseguite sul grafo, permettono di

individuare dei nodi che sicuramente saranno branch nella soluzione

finale. Fungono quindi da limite inferiore per quello che sarà il costo

della soluzione ottima del problema.

37

Di seguito vengono analizzate le 2 tipologie di lower bound utilizzate

per questo problema:

3.3.1.Stima nodi frontiere/foglie

Questo tipo di stima prevede di andare a contare il numero di nodi

foglia e di nodi frontiera presenti in una sottocomponente, dove per

sottocomponente si intendere l’insieme dei nodi raggiungibili a partire

da una frontiera. Se le foglie sono di più delle frontiere allora

sicuramente si può predire che nella soluzione finale sarà presente

almeno un nodo branch, poiché per costruzione è impossibile che ciò

non avvenga. Si osservi l’esempio in figura, dove le componenti sono

indicate dai quadrati azzurri e le frontiere corrispondono ai vertici

arancioni. Nella componente di sinistra troviamo 1 nodo frontiera e 2

nodi foglia. Infatti lo spanning tree per essa (evidenziato in rosso)

prevederà sicuramente almeno un nodo branch che nel caso

dell’esempio è il nodo 3. Invece nella componente di sinistra vi sono

un nodo foglia e due nodi frontiera e ciò rende possibile trovare una

soluzione con 0 nodi branch per quella componente.

38

Figura 6:stima nodi frontiera/foglie

3.3.2.Stima per eliminazione

Questa stima prevede di andare ad eliminare logicamente un nodo dal

grafo residuo e di verificare quante componenti connesse saranno

indotte da tale operazione. Se le componenti che si vengono a creare

sono più di 3 automaticamente si può affermare che quel nodo sarà un

branch nella soluzione ottima. Questo si può dire perché si verificano

due condizioni:

• Se eliminando il nodo si creano delle componenti connesse allora

sicuramente tale nodo deve essere presente all’interno un qualsiasi

spanning tree altrimenti non si potrebbe ottenere la copertura di

tutti i nodi del grafo.

• Inoltre se le componenti che si vengono a creare sono almeno 3

possiamo affermare che il nodo in questione è un nodo branch.

39

Nell’esempio seguente ,in figura A), se eliminiamo il nodo nove

(evidenziato in verde) otterremo 3 componenti connesse mostrate

nella figura B).

Figura 7(A): grafo prima dell'eliminazione del nodo 9

Figura 8(B): grafo dopo l'eliminazione del nodo 9

40

3.3.3.Stima per eliminazione doppia

Questa tipologia di stima è identica alla precedente con la differenza

che saranno eliminati due nodi alla volta. Vengono provate tutte le

possibili combinazioni di coppie nodi la cui eliminazione ha portato

alla creazione di 2 componenti durante la stima ad eliminazione

singola. Si è fatta tale scelta poiché è inutile considerare i nodi già

individuati come branch dalla stima precedente. Allo stesso modo, è

inutile considerare i nodi la cui eliminazione ha portato alla creazione

di 1 componente nella stima precedente poiché la probabilità che si

celi un nodo branch tra di essi è bassa. L’idea alla base è che se

eliminando k nodi da un grafo, si vengono a creare almeno k+2

componenti connesse allora sicuramente almeno uno dei due nodi sarà

branch per costrunzione. Si veda l’esempio in figura con

l’eliminazione di 2 nodi e la formazione di 4 camponenti. Qualunque

sia il modo con cui si connettano le componenti ai 2 nodi,vi sarà

sempre almeno un nodo branch (evidenziato in rosso).

Figura 9: esempio di stima per eliminazione doppia

Figura 10: esempio di stima per eliminazione doppia

41

4.Ottimizzazioni

Oltre all’esecuzione standard dell’algoritmo sono state introdotte della

ottimizzazioni in modo tale da poterne incrementare la velocità

d’esecuzione. Di seguito sono riportate le principali:

4.1.Split del problema

Essendo l’ MBV un problema NP-Hard, nel momento in cui inizia a

crescere la taglia del grafo in input i tempi di esecuzione cominciano a

diventare troppo onerosi, per tale motivo si necessita di tecniche per

ovviare a tale problema. Ad esempio può accadere che per istanze di

50 nodi i tempi di esecuzione siano vicini allo zero, mentre per istanze

di 100 i tempi tendano ad aumentare vertiginosamente. Per tale

motivo si è pensato al Graph Splitting, ossia ad una suddivisione del

grafo in 2 o più sotto-componenti che permettano esecuzioni

indipendenti dell’algoritmo. Tornando all’esempio precedente si

potrebbe pensare di suddividere il grafo di partenza in componenti

connesse ognuna di 50 nodi e poi di unire alla fine delle 2 esecuzioni,

i risultati. Questo permetterebbe di risolvere istanze di dimensioni

elevate in pochi secondi e soprattutto con una netta diminuzione delle

iterazioni dell’algoritmo.

Quest’ultimo aspetto risulta cruciale nella comprensione del vantaggio

dello split, poiché considerare tutti i possibili alberi ricoprenti di un

grafo di N nodi è molto più dispendioso che considerare tutti gli alberi

ricoprenti per due grafi di N/2 nodi e poi fonderli tra loro. Per rendere

meglio l’idea si può pensare ad una permutazione dei nodi del grafo.

Questo aiuta a comprendere che le permutazioni di 6 elementi siano

considerevolmente differenti da due permutazioni di 3 elementi

sommate tra loro:

42

� 6! = 6 x 5 x 4 x 3 x 2= 720

� 3! + 3! = 6 + 6 = 12

In più se si considera il tutto in un ambiente multi-processore, i

sottoproblemi potrebbero essere eseguiti contemporaneamente.

Ovviamente tale operazione non è sempre possibile altrimenti il

problema non verrebbe classificato come NP-Hard. Sono stati studiate

varie casistiche in cui poter applicare lo split del problema e di seguito

vengono riportate quelle utilizzate dall’algoritmo:

4.1.1.Split basato sulle frontiere

Dato che ad ogni passo dell’algoritmo viene calcolata la stima

frontiere/foglie per ciascuna sotto-componente, si è pensato di

inglobare le due cose in un’unica funzione. Nel momento in cui si

calcolano il numero di frontiere e di nodi foglia vengono ricavate le

diverse sotto-componenti, ognuna delle quali avrà al proprio interno

un set di nodi FRONTIERA. In pratica partendo da un nodo frontiera

si inseriscono nella stessa sotto-componente tutti i nodi raggiungibili.

Di conseguenza se da un nodo frontiera si riescono a raggiungere tutti

nodi (ATTIVI e FRONTIERA) vorrà dire che il grafo sarà costituito

da un’unica componente connessa e che quindi non sarà possibile

eseguire lo split del problema, viceversa tutti i nodi restanti non

ancora visitati apparterranno ad altre componenti. Più componenti si

ottengono e più il problema principale sarà scomposto in sotto

problemi. La presenza del set di Frontiere in ciascuna sotto componete

garantisce la corretta continuazione dell’algoritmo. Infine una volta

ottenuti gli spanning tree per ciascuna sotto-componente basterà

semplicemente fonderle con lo spanning tree del problema principale

ottenuto fino al punto di split ed il costo totale della soluzione sarà

43

ottenuto, sommando il numero di nodi branch per ogni componente.

Nell’esempio sono messe in evidenza le frontiere (nodi arancioni) e le

due componenti ( rettangoli azzurri) su cui sarà richiamato l’algoritmo

indipendentemente.

Figura 11:split basato su frontiere

4.1.2.Split basato sulle eliminazioni

Quest’altra variante di split viene lanciata solo se la prima non è

andata a buon fine. Anche questa è inglobata in un’unica funzione con

la rispettiva stima. Da come si può immaginare, nel momenti in cui un

nodo viene classificato come branch dalla stima vengono ricavate le

sotto-componenti indotte dall’eliminazione del suddetto nodo. In tal

caso però il nodo verrà inglobato nella componente in cui sono

presenti le frontiere, in quanto grazie alla modalità di esecuzione

44

dell’algoritmo tutti i nodi INATTIVI si troveranno da un lato,al centro

avremo i nodi FRONTIERA e all’altro capo del grafo avremo i

restanti nodi ATTIVI. Dato che elimineremo logicamente solo nodi

ATTIVI o FRONTIERA nel momento in cui si effettuerà lo split le

FRONTIERE ricadranno tutte nella stessa componente insieme al

nodo branch(o nodo di splitting). Nelle componenti restanti sarà

l’algoritmo a forzare alcuni nodi a diventare delle frontiere, in

particolare verranno scelti proprio i vicini del nodo branch. Il resto

dell’esecuzione è analogo a quanto visto per la prima tipologia di split.

C’è solo da specificare che, nel caso di più nodi branch individuati,

verrà scelto il branch la cui eliminazione comporta la creazione del

massimo numero di componenti di dimensione maggiore di 2.

4.1.3.Split in due componenti

Questa tipologia di split è un caso particolare dello split precedente.

Anche in questo per questo si frutta l’ eliminazione logica dei nodi,

ma piuttosto che considerare casi di nodi branch(ossia casi in cui si

creano almeno 3 sotto-componeti), ci si concentra sui casi in cui

dall’eliminazione di un nodo vengono a crearsi 2 sotto-componenti.

Non tutti i casi sono gestiti dall’algoritmo. Per motivi di semplicità

vengono gestiti i casi in cui le due componenti sono separate da un

unico ramo. Quindi il nodo di splitting al più potrà essere branch in

una sola componente(quella verso cui è collegato con almeno 2 archi).

45

Figura 12:split basato su eliminazione

Nel momento in cui si effettua lo split si possono creare due scenari:

a) il nodo individuato come nodo di split (il nodo azzurro) è collegato

con la componente che contiene le frontiere. In tal caso esso ed il

vicino appartenente all’altra componente(il nodo giallo) vengono

inseriti in questa componente. Il vicino sarà quindi duplicato in

entrambe le componenti per l’arco di tempo dell’esecuzione dello

split e gli verranno momentaneamente cancellati gli archi verso la

componente di appartenenza. Tutto ciò viene realizzato per fare in

modo che l’algoritmo tenga presente che il nodo di split ha anche

l’arco verso il vicino che deve essere preso in soluzione

obbligatoriamente affinchè la soluzione sia un unico albero

ricoprente e non una foresta. Infine per l’esecuzione dell’algoritmo

nella partizione restante sarà necessario rendere il “vicino”

frontiera (il nodo 5 arancione nella figura).

46

Figura 13:trasformazione delle componenti durante lo split

b) L’altro scenario invece prevede che il nodo di split (il nodo

azzurro) sia nella componente che non contiene la frontiera e

quindi il tutto avviene in maniera analoga al caso a) con la

differenza che il nodo di split ed il vicino verranno trattati in

maniera opposta al caso precedente.

4.2.Upper Bound

Nel momento in cui si applica uno split, l’esecuzione dell’algoritmo

subisce delle leggere variazioni. Ad esempio i lower bound vengono

applicati sulle singole sottocomponenti in modo da risultare più

precisi. In più è possibile sfruttare tali informazioni per poter ricavare

anche un upper bound per ciascuna componente. Tale upper bound

può essere calcolato come :

upperbound = sol. Incombente – sol. Attuale – altriLB

dove:

sol. Incombente: è la soluzione ottima corrente dell’intero problema.

sol. Attuale: è la soluzione delle componenti già calcolate.

altriLB: corrisponde alla somma dei lower bound delle

componenti ancora da calcolare.

Tale upper bound verrà passato al sotto problema e verrà utilizzato per

saltare determinati rami decisionali.

47

4.2.1.Euristica 1

Per il calcolo dell’upper bound l’algoritmo sfrutta anche un’euristica

che calcola con una semplice procedura una soluzione ammissibile.

Tale soluzione, nel caso sia più vantaggiosa dell’upperbound calcolato

come descritto precedentemente può sostituire quel valore o

addirittura nel caso abbia lo stesso costo del lower bound può essere

utilizzata come soluzione ottima per il grafo residuo, risparmiando

cosi tempo e cicli computazionali. In figura è mostrato un esempio di

grafo su cui sarà applicata l’euristica.

Figura 14:grafo dato in input all'euristica

L’euristica prevede i seguenti passi:

1. inserire in soluzione tutti gli archi che incidono su nodi di grado 1

eliminando tali nodi dal grafo di partenza.

48

Figura 15:grafo dopo l'eliminazione dei nodi di grado 1

2. se ci sono nodi frontiera non ancora visitati:vai al punto 3

altrimenti al 4.

3. partendo dalla frontiera si effettua una visita in profondità da nodo

a nodo inserendo di volta in volta gli archi che connettono tali nodi

in soluzione. Questa si fermerà se sono stati visitati tutti i nodi o se

si è giunti ad un nodo che ha vicini già tutti visitati. Torna al punto

2.

49

Figura 16:soluzione ammissibile individuata

4. se ci sono nodi attivi non ancora visitati:vai al punto 5 altrimenti

FINE.

5. partendo dal nodo attivo si effettua una visita in profondità da nodo

a nodo inserendo di volta in volta gli archi che connettono tali nodi

in soluzione. Questa si fermerà se sono stati visitati tutti i nodi o se

si è giunti ad un nodo che ha vicini già tutti visitati. Torna al punto

4.

4.2.2.Euristica “Suggeritore”

Questo tipo di euristica è molto simile alla precedente in quanto

partendo da ogni nodo frontiera si scende in profondità nel grafo

cercando di coprire tutti i nodi.

Ogni volta che un nodo assume un grado in soluzione uguale a 2,

automaticamente vengono selezionati tutti i suoi figli nella speranza di

50

poter minimizzare il costo della soluzione finale. L’euristica prevede

le seguenti strutture:

• Stack: che contiene i nodi che hanno grado 1 in soluzione e per i

quali si dovrà scegliere un figlio su cui spostarsi.

• Vettore nextBranch: in tale vettore sono presenti tutti i nodi che

hanno grado due nella soluzione e che sono quindi candidati a

diventare nodi branch nella soluzione finale.

• Vettore Branch: che conterrà tutti i nodi settati a branch.

L’euristica prevede i seguenti passi:

1. Si inizializza lo stack con tutti i nodi frontiera (per i quali si

considera già un grado pari a 1, in quanto ognuno di essi è

collegato ad un nodo INATTIVO).

2. Finchè la lo stack non è vuoto:

3. Ad ogni passo si estrae il top dello stack e lo si rimpiazza con

un suo figlio. Nel caso il nodo sia già “fleggato” come branch

allora verranno inseriti tutti i suoi figli nello stack.

4. Il nodo estratto dal top dello stack viene inserito nel vettore

nextBranch. Tale nodo avrà grado due nella soluzione (grazie

agli archi che lo collegavano al padre ed al figlio).

5. Se lo stack è vuoto e sono stati tutti i nodi, termina l’esecuzione.

6. altrimenti si seleziona tra i nodi del vettore nextBranch, quello

con un maggior numero di nodi non ancora visitati e lo si

reinserisce nello stack considerando il fatto che ora questo nodo

è un branch perchè il suo grado in soluzione è pari a 3,torna al

punto 2.

7. Al termine della procedura tutti i nodi Branch sono inseriti

nell’apposito vettore Branch.

51

Il vettore Branch verrà passato alla procedura per il calcolo del

lowerbound basata su eliminazione. Questo perché si è pensato di

lanciare la suddetta stima solo sui nodi che l’euristica ha evidenziato

come branch, in quanto sicuramente, in una qualsiasi soluzione

ammissibile, saranno presenti i cosidetti nodi “branch certi”, ossia

quei nodi che saranno presenti con certezza nella soluzione ottima.

4.2.3.Ricerca Locale

Tale procedura prende in input la soluzione ottenuta da una delle due

euristiche e cerca di migliorarla. L’idea alla base prevede di partire dai

nodi foglia della soluzione e di verificare se collegandoli ad un altro

nodo, mediante un arco presente nel grafo originale, si riesce ad

ottenere una soluzione di costo minore. Tale mossa comporta la

creazione di un ciclo. Una volta ottenuto quest’ultimo, si individua

l’arco che eliminato porta ad uno spanning tree migliore di quello di

partenza. Si può parlare di miglioramento se il peso dell’arco che si va

ad inserire(p1) è minore del peso dell’arco che si elimina(p2). Ovvero

se p2 > p1. Il peso di un arco è stabilito come la somma dei pesi dei

due nodi incidenti su di esso. Il peso di un nodo è stabilito in base alla

seguente tabella:

Grado Peso

≤2 0

>3 1/grado

3 1

Il valore di p2 quindi può essere:

52

• p2 ≥ 1, se si elimina un arco tra un nodo branch di grado 3 ed un

suo vicino. Questa è la scelta prioritaria in quanto permette di

diminuire il costo della soluzione.

• p2=1 / |v1| + |v2| , dove v1 e v2 sono i vertici incidenti sull’arco

da eliminare.

Si veda l’esempio in figura in cui la soluzione iniziale da migliorare è

quella evidenziata dagli archi celesti:

Figura 17:soluzione ammissibile presa in input dalla procedura

Di seguito vengono analizzati i 2 casi per chiarire le idee:

1. caso di inserimento di un arco tra due foglie:

tale arco avrà peso p1=0, perché aggiunto tra due nodi foglia che

hanno entrambi grado 1. Ciò è evidenziato nell’esempio

successivo, in quanto viene eliminato l’arco <3,4> di peso 1 in

favore del arco <4,7> di peso 0.

53

Figura 18:primo caso di miglioramento

2. caso di inserimento di un arco tra una foglia e un nodo branch:

tale arco avrà peso p1=1/|v+1| , dove v è il nodo branch preso in

considerazione. Nell’esempio viene eliminato l’arco <3,5> di peso

1 in favore di <2,5> di peso 1/4.

Figura 19:secondo caso di miglioramento

54

4.3.Parental Semplification

Questo tipo di ottimizzazione è stata introdotta per fare in modo da

evitare che si visiti più di una volta la stessa configurazione d’albero.

Si veda l’esempio seguente:

Figura 20: grafo di partenza dalla procedura

Per questo esempio di grafo sono possibili due soluzioni evidenziate

in arancione di seguito:

Figura 21:2 possibili soluzioni ammissibili

55

Queste soluzioni sebbene prevedano archi differenti risultano

praticamente identiche ai fini del problema. L’obiettivo è quello di

evitare che da entrambi i nodi 2 e 3 vengano scansionate le strade che

porta al 4 e al 5. Tale funzione fa in modo che se è scansionata la

strada che porta alla soluzione con gli archi <2,4> e <3,5>, non verrà

scansionata anche la strada che porta alla soluzione con gli archi

<2,5> e <3,4>.

Sono state implementate due differenti varianti:

4.3.1.Basata su eliminazione

Per la comprensione di tale funzione si veda l’esempio nella figura

seguente:

Figura 22:configurazione parenal semplification ad eliminazione

Si consideri che si voglia aggiungere alla soluzione che si sta

costruendo, l’arco che va dal nodo padre (P) al nodo figlio (F*). Prima

di aggiungere tale ramo si verifica :

1. se F* ha un arco nel grafo originale che lo collega ad un nodo

attualmente FRONTIERA (F rosso, in figura) vai al passo 2.

2. se F ha un vicino non ancora selezionato (N) che a sua volta ha

un ramo non ancora selezionato verso P allora vai al passo 3.

3. si consideri Ki la chiave del nodo i-esimo:

56

se KP > KF e KF* > KN oppure se KP < KF e KF* < KN

allora aggiungi alla soluzione il ramo <P,F*> altrimenti

eliminalo. Grazie a questo tipo di controllo si garantisce che si

scansioni una sola delle due soluzioni messe in evidenza in

precedenza.

Se si considera l’esempio precedente, si ha che KP = 3, KF = 2 , KF* =

5 , KN = 4. Ammettendo che si voglia aggiungere il ramo <3,5> e che

sussistano le condizioni 1 e 2 suddette allora il ramo sarà inserito in

soluzione e ciò porterà all’ottenimento della soluzione sulla destra

della figura precedente. Questo perché 2 < 3 e 4 < 5.

4.3.2.Basata su Inclusione

Questo tipo di ottimizzazione può essere utilizzata nel seguente caso:

Figura 23:configurazione parental semplification per inclusione

Da come si può notare si ha che il nodo 2 ha l’insieme di figli(4, 5)

incluso nell’ insieme di figli del nodo 3 (4,5,6). Anche tale procedura

57

permette di decidere se provare o meno ad inserire un arco nella

soluzione che si sta costruendo a seconda della configurazione che si

viene a creare. Ad esempio prima di aggiungere il ramo tra il nodo 1

ed il nodo 3 si verifica che:

1. se esiste un fratello del nodo 3 che ha un set di figli incluso in

quello del nodo 3,in questo caso il nodo 2, allora si può scartare

l’arco <1,3> .

2. Se i nodi 2 e 3 avessero avuto lo stesso identico set di figli allora si

sarebbe utilizzata la stessa tecnica basata sulle chiavi usata nel caso

precedente.

Quindi la scelta che in generale si predilige è quella del nodo di grado

più basso.

4.4.Ordinamento

Si è deciso di processare le componenti connesse di un grafo

individuate durante la fase di split, con uno specifico ordine. Tale

ordine dipende da una priorità associata ad ogni componente che è

ottenuta con il seguente calcolo:

(upperbound-lowerbound)/taglia componente

Questa scelta è stata presa in quanto si è pensato che processando

prima le componenti per cui si ha più possibilità di ottenere un valore

ottimo molto grande. In questo modo è possibile risfruttare tal valore

nel calcolo degli upperbound per le componenti non ancora

processate. Ma considerato che si conosce l’ottimo incombente, se gli

ottimi per le componenti già processate sono grandi allora molto

probabilmente il seguente calcolo:

58

upperbound = sol. Incombente – sol. Attuale – altriLB

determinerà un upperbound per le componenti restanti più prossimo

al lowerbound e quindi più preciso.

Si è pensato inoltre di applicare l’ordinamento anche durante la fase di

scelta, che si verifica quando ci si trova su un nodo INATTIVO e

bisogna stabilire su quale vicino spostarsi. In tal caso si è pensato di

ordinare i vicini del nodo INATTIVO per grado.

59

5.Gestione della memoria

Al fine di rendere il software più veloce si è deciso di avere un

peggioramento in termini di spreco memoria allocata. Dato che ogni

chiamata a sistema per l’allocazione di memoria(ad esempio per i

vettori) richiede tempo si è deciso di istanziare all’inizio

dell’esecuzione dell’algoritmo tutte le strutture e gli array utilizzate

durante la fase di esecuzione. Ciascuna di esse è stata inizializzata al

valore massimo di elementi che si può raggiungere durante

un’esecuzione (il più delle volte si è istanziato al numero di nodi del

grafo preso in input).

Tale algoritmo è stato idealizzato pensando ad un esecuzione multi-

thread su diversi processori. Ciò fa si che ogni qualvolta l’algoritmo si

divida in vari sottoproblemi (fase di split) ognuno di essi re-istanzi un

nuovo algoritmo che possa essere eseguito indipendentemente. Per

venire incontro a tale necessità all’inizio della sua esecuzione viene

anche istanziato vettore di algoritmi utilizzati all’occorrenza di uno

split. La taglia di tale vettore ovviamente dipende dal numero di nodi

del grafo in input.

Ciò è molto più conveniente in termini di tempo, piuttosto che

doverne istanziare uno ogni qualvolta si verifica uno split. Si veda

l’esempio seguente. Dato il grafo iniziale:

60

Figura 24:un esempio di grafo

Considerando che l’algoritmo parta dal nodo 1. Solo quando giunge al

nodo 5 si accorge della possibilità di poter splittare. Il problema è che

l’algoritmo può giungere al nodo 5 in molti modi e che quindi

eseguirà lo stesso split più volte. Si veda l esempio:

Figura 25:evidenziati 2 possibili cammini dalla radice al nodo 7

61

Per tal motivo non conviene ogni volta istanziarne uno nuovo ma

basta estrarne uno disponibile dal vettore ed inizializzarlo.

62

6.Struttura codice

Di seguito è spiegato come risulta essere strutturato il codice

dell’algoritmo.

6.1.Class Diagram

Figura 26:class diagram

• Parser: classe utilizzata per la lettura di un grafo in input da un

file di testo.

• SottoProblemi: classe che implementa la struttura che gestisce i

vari sottoproblemi di cui un’istanza necessita.

• Cestino: è utilizzato per la memorizzazione e il ripristino degli

archi che vengono eliminati ad ogni passo dell’algoritmo.

63

• Soluzione: implementa la soluzione come un vettore di coppie di

nodi.

• Grafo: è la classe che implementa il grafo preso in input .

• BeB: implementa la versione dell’algoritmo che lavora sulla

radice.

• Mbv: implementa la versione dell’algoritmo che lavora su un

generico nodo non radice del grafo.

6.2.Struttura del metoto “ottimo()” di Mbv Di seguito è indicata la struttura del codice del metodo “ottimo” della

classe Mbv. Tale metodo è ricorsivo ed è il cuore dell’algoritmo

sviluppato.

64

Figura 27:struttura metodo "ottimo"

65

7.Risultati Di seguito vengono visualizzati i risultati appurati su diverse istanze

prese in esame. Questi indicati sono solo dei test parziali che dovranno

essere integrati con altri casi di test. Le istanze sono suddivise in 5

classi che variano per numero di nodi (20,40,60,80,100). Per ogni

classe sono stati scelti grafi con una densità variabile. Nella tabella

sono indicate le istanze nella prima colonna dove per ciascuna sono

indicati il numero di nodi e quello di archi più un intero identificativo.

I risultati dell’algoritmo sono stati messi a confronto con quelli del

risolutore matematico Cplex.

B&B Cplex Istanza Ottimo Tempo(sec) Tempo(sec)

Spd_RF2_20_27_227.txt 2 0 0,0300 Spd_RF2_20_34_259.txt 1 0 0,0200 Spd_RF2_20_42_291.txt 1 0 0,0500 Spd_RF2_20_49_331.txt 0 0 0,0100 Spd_RF2_20_57_379.txt 0 0 0,0400 Spd_RF2_40_50_611.txt 8 0 0,0200 Spd_RF2_40_60_651.txt 3 0 0,2100 Spd_RF2_40_71_707.txt 2 0 0,1700 Spd_RF2_40_81_739.txt 1 0 0,2800 Spd_RF2_40_92_787.txt 1 0 0,2500 Spd_RF2_60_71_1027.txt 13 0 0,1600 Spd_RF2_60_83_1059.txt 7 0,015 0,2900 Spd_RF2_60_95_1091.txt 7 0.093 0,4200 Spd_RF2_60_107_1155.txt 4 7.26 0,4200 Spd_RF2_60_119_1179.txt 2 24,741 3,7600 Spd_RF2_80_93_1427.txt 17 0,015 0,1500 Spd_RF2_80_106_1459.txt 12 0,015 0,4300 Spd_RF2_80_120_1491.txt 8 3,65 1,1900 Spd_RF2_80_133_1555.txt 5 64,226 1,3800 Spd_RF2_80_147_1579.txt 4 66,269 1,8200 Spd_RF2_100_114_1811.txt 26 0,031 0,5200 Spd_RF2_100_129_1851.txt 18 18,236 2,7500 Spd_RF2_100_144_1891.txt 12 176,686 5,1000 Spd_RF2_100_159_1931.txt 8 1122,9 5,7400 Spd_RF2_100_174_2003.txt 4 3650,99 11,5800

66

Nei casi di densità molto bassa o molto alta si è riuscito a battere le

performance del software suddetto. Questo perché nel caso di bassa

densità era più probabile che si creassero le condizioni per scomporre

il problema in sottoproblemi mediante lo split, mentre nei casi in cui

la densità era molto alta c’erano molte probabilità di trovare subito

una soluzione di costo molto basso (magari di valore 0) che

permetteva cosi di tagliare l’albero decisionale fin da subito.

Mediamente, in tutti i casi restanti il risolutore matematico converge

alla soluzione più velocemente dell’ algoritmo sviluppato.

67

8.Conclusioni e futuri sviluppi

Sebbene i risultati siano soddisfacenti, purtroppo non si è ottenuto il

miglioramento che ci si aspettava dall’introduzione degli split perché

come già accennato nel capitolo 5, può accadere che se gli split non

vengono eseguiti già dalla prima iterazione dell’algoritmo, quando

cioè ancora non sono state prese delle scelte dell’albero decisionale,

accade che tali split non porteranno ad una reale scomposizione del

problema. Come si può vedere nella figura che segue ci sono varie

strade da poter esplorare fino al nodo 5 (punto di split) e di

conseguenza split simili verranno applicati più volte.

Figura 28(A):esempio split inutile

Purtroppo non è detto che il valore ottimo per le 3 componenti

individuate sia sempre lo stesso per ciascuna, in quanto sulla base

della strada intrapresa l’algoritmo avrà cancellato o meno determinati

archi sulla base del set di frontiere. Nel caso raffigurato sopra la

componente (23,7,20) prevederà sicuramente il nodo 23 come branch,

68

mentre nella figura che segue la soluzione per la componente

(4,23,7,20) ha valore ottimo sarà 0.

Figura 29(B): esempio di split inutile

Infine per gli sviluppi futuri si è pensato ai seguenti miglioramenti:

• Eliminare dal grafo tutti i nodi foglia fino ad ottenere un grafo

con nodi di grado maggiore di 1.

• Ottimizzare il codice durante la scelta del singolo vicino su cui

spostarsi, evitando di lanciare le stime per il calcolo del

lowerbound.

• Velocizzare la stima per eliminazione memorizzando

informazioni ed evitando cosi di doverla lanciare troppe volte.

• Memorizzare l’ottimo per una sezione di grafo in modo da

poterne risfruttare il valore nel momento in cui si identifica una

sezione che prevedere lo stesso set di nodi frontiera e nodi

attivi.

69

Bibliografia [1] L. Gargano, P. Hell, L. Stacho, and U. Vaccaro. “Spanning

trees with bounded number of branch vertices”. Lecture notes in computer science, pages 355-365,2002.

[2] R. Cerulli, M. Gentili, and A. Iossa. “Experimental comparison

of algorithms for bounded-degree spanning tree problems. Computational Optimization and Applications”.

[3] C.Cerrone, M.Gaudioso. “Omega, our multi ethnic algorithm” .

Capitolo 3. [4] L. Gargano, M. Hammar. “There are spanning spiders in dense

graphs (and we know how to find them)”. Lecture notes in computer science, pages 802-816,2003.

[5] F.Carrabs, R.Cerulli, M.Gentili, M. Gaudioso. “Lagrangian

approach for bounded-degree spanning tree problem”.

[6] R Ahyja, T Magnanti, and J Orlin. “Network ows: theory,

algorithms, and applications. cdsweb.cern.ch.”.