Politecnico di Torino
Tesi di Laurea
Ottimizzazione topologica di reti
di tipo Internet Protocol con il
metodo del Local Branching
Relatore:
Candidato:
prof. Roberto Tadei
Flavio Cimolin
Dicembre 2003
Un problema di Network Design
Le componenti del problema sono:
• Un insieme di nodi
• Una serie di archi fra i nodi
• Delle richieste che devono essere instradate sulla rete
Su ogni arco possono essere installati dei link
(cavi in fibra ottica), con un certo costo unitario
ed una determinata capacità. Ogni arco presenta
poi dei pesi di instradamento in entrambe le
direzioni di percorrenza
Si deve garantire il corretto instradamento di
tutti i flussi secondo un protocollo di tipo
Internet Protocol OSPF-ECM
Problema:
Determinare la topologia di costo minimo e l’allocazione
della banda in modo da soddisfare tutte le richieste
Modello in PLMI
Variabili
Insiemi
Vincoli
Solver
Funzione
Obiettivo
Istanza
Xpress IVE ed il linguaggio Mosel
•
•
Xpress IVE è un software di ottimizzazione della Dash Optimization che si basa
sul linguaggio Mosel
Mosel è un linguaggio di programmazione particolarmente indicato per scrivere
modelli di Programmazione Lineare
Output
Variabili e vincoli
Albero di ricerca,
Statistiche,
Grafici di progresso
Listato del programma
Branch and Bound
•
•
•
•
•
E’ lo strumento base per risolvere problemi di PLMI
E’ un metodo di tipo enumerativo con uno schema ad
albero
Ad ogni passo sceglie una variabile frazionaria e genera
due sottoproblemi imponendone l’interezza
Sfrutta dei rilassamenti del problema
Consente di eliminare interi sottoinsiemi di soluzioni in
base a 3 criteri di fathoming:
1. Inammissibilità della soluzione
2. Soluzione intera determinata
3. Assenza di soluzione migliorante
Euristiche basate su ricerca locale
Permettono di determinare in breve tempo soluzioni
molto buone, ma senza poterne garantire l’ottimalità
Si può descrivere l’algoritmo in quattro passi fondamentali:
1. Si parte da una soluzione iniziale di riferimento x1
2. Si definisce un vicinato V, cioè un insieme di soluzioni
“vicine” a x1
3. Si cerca all’interno del vicinato una soluzione x2
migliore della precedente
4. Si reitera il procedimento creando un nuovo vicinato di
x2 e cercando lì una soluzione ancora migliore
Meta-Euristiche
Le euristiche classiche hanno il rischio di subire
intrappolamenti
in
minimi
locali,
per
risolvere
l’inconveniente nascono le Meta-Euristiche
Diversificazioni
A volte conviene accettare
una soluzione peggiorante
per poter uscire da minimi
locali e sondare più soluzioni
ammissibili
Metodi di Tabu Search, Simulated Annealing, Algoritmi Genetici
IL LOCAL
BRANCHING
Il Local Branching
• Presentato per la prima volta da M. Fischetti e
A. Lodi nel Maggio 2002
• E’ in linea di principio un metodo esatto, ma può
essere utilizzato in modo proficuo come una metaeuristica
• Si basa sulla costruzione di vicinati in cui un certo
numero di variabili vengono fissate, ma non si sa a
priori quali
Soft Variable Fixing:
E’ il Solver stesso a decidere quali variabili fissare e
quali lasciare libere, facendo la scelta ottima
Variabili Binarie
• Il Local Branching si applica bene a
problemi che hanno un elevato numero di
variabili binarie (0/1)
• Necessita di una soluzione iniziale di
riferimento
• A partire da essa, crea un vicinato che
contenga le soluzioni in cui cambino valore
al massimo k variabili binarie
Tagli di Local Branching
Sia B l’insieme di tutti gli indici delle variabili binarie, e sia S il
supporto binario di
, ovvero l’insieme degli indici delle variabili
binarie che hanno valore 1:
Si definisce allora Taglio di Local Branching di ampiezza k il
vincolo aggiuntivo:
Scelto k sufficientemente piccolo, l’intorno che ne risulta può
essere esplorato interamente al fine di trovare una soluzione
migliore x2, e così via…
Schema ad albero
Ne deriva uno schema ad albero molto simile al Branch and
Bound classico
Si impone un taglio
di Local
Branching
Si parte
dalla
soluzione
iniziale
Si esplora interamente il
vicinato che ne deriva, con
un “Tactical Branching”
Viene trovata una soluzione migliore
Allora resta solo più la possibilità di
IlSiprocedimento
continua
reitera
il procedimento
con alaquando
nuova
effettuare
una
ricerca fino
esaustiva
su
nel
nodoledideterminata
sinistra soluzioni
non viene determinata
soluzione
tutte
restanti
nessuna soluzione migliore
ed il suo opposto
Tagli di Local Branching
Inserimento di un tempo limite
•
•
Quando si ha a che fare con problemi complessi (è il nostro caso), anche la
ricerca sul ramo di sinistra può risultare troppo dispendiosa da poter essere
portata a termine
Si inserisce allora un tempo limite nella ricerca, oltre il quale fermarsi (nel
caso sia già stata determinata una soluzione intera migliore della
precedente)
Si apre un nuovo ramo aggiungendo
un taglio di Local Branching relativo
alla nuova soluzione determinata
Non si può in questo
Tempo limite raggiunto
caso invertire questo taglio,
perché
il suo intorno
Determinata
unanon è
stato nuova
esplorato
interamente
soluzione
Metodo del Local Branching
• Oltre al tempo limite si possono anche introdurre
delle diversificazioni
• Si abbandona così la struttura di metodo esatto
• Non si arriverà mai all’esplorazione dell’ultimo
nodo di destra
• Il comportamento rispecchia così quello di una
meta-euristica, e può determinare in tempi brevi
soluzioni sempre migliori, ma senza garantirne
l’ottimalità
Applicazione al
problema in esame
Variabili di Local Branching
Il problema in esame presenta effettivamente un
cospicuo numero di variabili binarie, fissate le quali il
problema diventa “semplice”
Sono le variabili y{i,j} , una per ogni arco presente nella
rete, ed indicano se esso deve essere aperto oppure no
TAGLIO DI LOCAL BRANCHING
dove
Sono stati studiati i vicinati per k = 1 (piccolo), 3 (medio), 5 (grande)
Soluzione Iniziale
E’ necessaria per far partire il metodo
Sono state testate due tipi diversi di soluzioni iniziali
MAGLIA COMPLETA
Tutti gli archi
vengono posti aperti
ALBERO RICOPRENTE
di costo minimo
Il minor numero possibile
di archi viene aperto
Istanze analizzate
• Per reti con 3, 4 e 5 nodi il Solver risolve il
problema in frazioni di secondo
• Per una rete con 6 nodi e richieste fra tutte le
possibili coppie di nodi il Solver non trova
soluzioni in 24 ore
Occorre analizzare istanze intermedie
Nodi di destinazione
• La complessità dell’istanza dipende dal numero di
nodi di destinazione (insieme DK)
• Sono allora state studiate numerose istanze da 6 e
da 7 nodi, nelle quali non tutti i nodi erano
destinazione di qualche richiesta
• Per ognuna di esse si sono fatti variare i parametri
caratteristici (k, tempo limite, tipo di istanza iniziale)
• Per questi casi si è confrontato il comportamento del
metodo del Local Branching con quello del metodo
esatto (Branch and Bound)
Risultati ottenuti
Se i parametri di tempo limite, dimensione del vicinato e
soluzione iniziale vengono settati con accuratezza, il Local
Branching funziona meglio del Branch and Bound
•
La soluzione iniziale “albero ricoprente di costo minimo” funziona
meglio di quella “maglia completa”
•
Il valore di k migliore è 3 (vicinato di medie dimensioni)
•
Il valore di tempo limite più opportuno è di scegliere sempre la prima
soluzione determinata (strategia first improvement)
Il metodo risulta però sempre troppo lento per istanze
grandi dato che l’algoritmo non riesce
ad interagire bene con il Solver.
Esempio di confronto
Istanza da 6 nodi, con 3 nodi di destinazione, k = 3, strategia first improvement,
soluzione iniziale albero ricoprente di costo minimo
Effetto “bandiera italiana”
Istanza da 7 nodi, con 3 nodi di destinazione, k = 3, strategia first improvement,
soluzione iniziale maglia completa
Sviluppi futuri
Il metodo è molto buono in linea teorica, ma nella
pratica non riesce ad essere efficiente per istanze grandi:
la causa è la scarsa interazione fra algoritmo e Solver
Si dovrebbe far capire al Solver che le variabili primarie sono le y{i,j}
Per istanze di grandi dimensioni si potrebbe ancora:
• studiare altre soluzioni iniziali (ad esempio ottenerne una con
una euristica costruttiva)
• valutare vicinati di dimensioni basse: k = 1, 2, 3
• implementare diversificazioni
FINE