Ottimizzazione topologica di reti di tipo Internet Protocol con il metodo del Local Branching

Vincoli per il calcolo dei cammini minimi:

d d d Ω d

π − π ≤ w + ²(y − 1) + M (1 − y ) + (² − w − w )y (2.6)

ij ij ji

{ij}

i j ij ji

∀(i, j) ∈ A, ∀d ∈ D

K

Vincoli relativi agli archi aperti:

d d

y + y ≤ y ∀d ∈ D , ∀{i, j} ∈ E (2.7)

K

{ij}

ij ji

Vincoli di rafforzamento del modello (sono già presenti implicitamente al-

l’interno dei precedenti, ma la loro aggiunta permette di escludere alcune

soluzioni non intere e quindi non ammissibili nello spazio delle soluzioni):

Λ

x ≤ M y ∀{i, j} ∈ E (2.8)

{ij} {ij}

{ij}

y ≤ x ∀(i, j) ∈ E (2.9)

{ij} {ij}

Riepiloghiamo infine i domini delle variabili:

y ∈ {0, 1} ∀{i, j} ∈ E

{ij} N

x ∈ ∀{i, j} ∈ E

{ij}

d

y ∈ {0, 1} ∀d ∈ D , ∀(i, j) ∈ A

k

ij R

d

f ∈ ∀d ∈ D , ∀(i, j) ∈ A

k

ij R

d

π ∈ ∀d ∈ D , ∀i ∈ N

k

i

2.3 Implementazione del modello in Xpress Mosel

L’implementazione in linguaggio Mosel ha dovuto necessariamente tenere

conto di una serie di accorgimenti che andremo a descrivere.

Anzitutto, vista la grande mole di dati relativi ad un’istanza del proble-

ma (descrizione della topologia della rete, costi di instradamento, costi dei

links, richieste), è stato necessario creare un file di dati apposito per ogni

istanza su cui applicare il modello. Ad esempio, un file di dati del tipo

“istanza 6n 20r.dat” contiene i dati relativi ad un’istanza da 6 nodi e 20

richieste. Il file di dati viene letto dal programma in fase di inizializzazione

in modo da acquisire tutte le costanti necessarie. Per un esempio effettivo

di file di istanza, vedere l’Appendice B.

Per come è stato formulato il modello, esso presenta casi in cui formal-

mente sarebbe necessario costuire array di insiemi, cosa che non è possibile

9

effettuare in automatico con i comandi del linguaggio mosel. E’ stato dunque

necessario aggirare il problema costruendo per ognuno di questi array una

matrice strutturata da usare in sostituzione dell’insieme che si voleva de-

scrivere. Per vedere come si è risolto il problema nei vari casi specifici, si

rimanda all’Appendice A, ove è riportato il listato del programma con i rela-

tivi commenti esplicativi. L’utilizzo di matrici opportunamente strutturate

in luogo di insiemi è stato effettuato principalmente per gli insiemi O e k .

d od

Analogamente, al fine di utilizzare anche gli insiemi A degli archi ed E

degli spigoli, che nel linguaggio mosel non potrebbero essere costruiti come

“coppie di elementi di N ” quali sono, si è fatto uso della matrice di incidenza

nodi-nodi (nel programma indicata con T ). Essa, contenendo i dati relativi

alla topologia della rete, può essere utilizzata molto vantaggiosamente per

caratterizzare i suddetti insiemi. Per esempio, la scrittura formale

∀ (i, j) ∈ A ...

può essere inserita nel programma con la sintassi

forall(i in N, j in N | T(i,j) = 1) ...

dove T (i, j) vale 1 se l’arco (i, j) è in topologia, 0 altrimenti. Quanto

all’insieme degli spigoli, per trascrivere la scrittura

∀ {i, j} ∈ E ...

basta allora aggiungere

forall(i in N, j in N | i<j and T(i,j) = 1) ...

con la convenzione che nel caso ci si riferisca ad uno spigolo {i, j} anziché

ad un arco (i, j), si consideri i < j.

Seguendo la stessa linea di principio, al fine di ridurre il più possibile il

numero di variabili effettive del modello (e dunque il costo computazionale),

risulta allora opportuno definirle in modo da evitare inutili ripetizioni. In

primo luogo questo si verifica quando una variabile definita su un arco non

dipende dalla direzione, nel qual caso basta ovviamente memorizzare l’infor-

mazione una volta sola. Inoltre vista la possibile mancanza di collegamenti

fra due nodi qualsiasi della rete, è molto conveniente memorizzare solamente

quelle variabili che davvero sono necessarie per risolvere il problema, e non

memorizzare proprio quelle che andrebbero poste a zero. E’ per questo che

tutte le variabili fondamentali del modello sono state definite attraverso ar-

ray dinamici, che permettono la creazione solo ed esclusivamente degli indici

effettivamente utilizzati. Il comando che permette di fare questo è create.

Vediamo ad esempio il caso dell’inizializzazione delle variabili y, che servono

ad indicare se uno spigolo è presente oppure no nella topologia corrente. Si

procede allora in questo modo: 10

declarations

y: dynamic array(N,N) of mpvar

...

end-declarations

forall(i in N, j in N | i<j and T(i,j) = 1) do

create(y(i,j))

...

end-do Λ

Un’ultima nota riguarda le costanti M , che comparendo in un vin-

{ij}

colo di rafforzamento, non hanno lo scopo di rappresentare una limitazione

vera e propria al numero di links installabili su uno spigolo {i, j}, bensı̀ di

irrobustire il modello, e dunque sono state poste convenzionalmente tutte

uguali a 100. 11

Capitolo 3

Metodi per la

Programmazione Lineare

Misto-Intera

3.1 Branch and Bound

Il metodo del Branch and Bound è stato introdotto agli inizi degli anni ’60 ed

è attualmente lo strumento base per la ricerca di soluzioni per un problema

di Programmazione Lineare Misto-Intera (PLMI). Si tratta di un metodo di

enumerazione implicita, caratterizzabile da uno schema ad albero che per-

mette di tenere traccia dell’enumerazione delle soluzioni, assieme ad una

procedura di valutazione del nodo (bounding procedure), grazie alla quale è

possibile scartare quei rami che non potranno mai condurre alla soluzione

ottima del problema.

L’enumerazione di tutte le possibili soluzioni ammissibili del problema risul-

terebbe infatti inapplicabile date le enormi dimensioni computazionali con

cui si avrebbe a che fare, e dunque metodi di questo tipo possono essere

estremamente efficaci in quanto riescono ad eliminare interi sottoinsiemi di

soluzioni, riducendo la ricerca solo ai rami che potrebbero contenere una

soluzione ottima.

Consideriamo un problema di minimo P contenente sia variabili intere,

0

sia variabili reali (PLMI). Il metodo del Branch and Bound partiziona allora

l’insieme delle soluzioni ammissibili in sottoinsiemi via via più ristretti, e per

ciascuno calcola un limite inferiore della funzione obiettivo. Per calcolare

tale lower bound si usano dei rilassamenti. Un rilassamento di un problema

si ottiene ignorando uno o più vincoli del problema stesso in modo da render-

lo più semplice al fine di trovare una soluzione in un tempo breve. La tecnica

più utilizzata è il rilassamento continuo: i vincoli eliminati sono quelli di

interezza delle variabili. Al problema P viene cosı̀ associato il problema

0

P L a variabili continue, che dunque può essere risolto in un tempo molto

0 12

più breve. Nel caso la soluzione di P L sia anche soluzione di P , cioè ab-

0 0

bia le variabili richieste intere, allora abbiamo già determinato la soluzione,

altrimenti si effettua un branch, cioè si sceglie una variabile x con valore

h

frazionario x̄ è si costruiscono i due sottoproblemi P e P uguali a P ma

1 2 0

h

con in aggiunta il vincolo: x ≤ bx̄ c per P

1

h h

x ≥ dx̄ e per P

2

h h

dove bx̄ c e dx̄ e sono rispettivamente l’arrotondamento per difetto e per

h h

x̄ .

eccesso di h

La soluzione intera del problema P dovrà a questo punto trovarsi ne-

0

cessariamente o in P oppure in P : abbiamo ridotto il problema in due

1 2

sottoproblemi leggermente più semplici.

L’operazione di branch può essere rappresentata visivamente come una

biforcazione che a partire da un nodo padre genera due nodi figli, come in

Figura 3.1. Figura 3.1: Operazione di branch

Lo stesso procedimento viene poi applicato ad ogni nodo figlio, ed in

questo modo si riescono ad ottenere sottoproblemi sempre più vincolati e

dunque più “facili” da risolvere, oltre che aventi con maggiore probabilità

una soluzione intera.

Esistono poi dei criteri, detti criteri di fathoming (potatura) che per-

mettono, in fase di costruzione dell’albero di ricerca, di stabilire se il nodo

corrente debba essere chiuso oppure no. Le possibilità che si presentano

dopo la risoluzione del rilassamento continuo in un generico nodo sono le

seguenti:

• inammissibilità della soluzione: non esiste soluzione ammissibile

del problema rilassato, dunque il nodo può essere chiuso

13

• non interezza della soluzione: il problema viene suddiviso in prob-

lemi figli come descritto in precedenza, dunque è un possibile candidato

per soluzioni intere

• soluzione intera: la soluzione del problema rilassato è intera, dunque

il nodo può essere chiuso perché non necessita di ulteriori ricerche; se

tale soluzione è migliore della migliore soluzione intera finora ottenuta,

quest’ultima viene aggiornata

• assenza di soluzione migliorante: se il lower bound del nodo

(che costituisce peraltro una stima ottimistica del valore della migliore

soluzione ottenibile a partire dal nodo corrente) è maggiore del valore

della funzione obiettivo della migliore soluzione intera finora determi-

nata, allora sicuramente sarà impossibile trovare soluzioni miglioranti

fra i nodi figli del nodo corrente, e dunque anche in questo caso esso

può essere chiuso

Infine è necessario definire la strategia di esplorazione dell’albero di ricer-

ca (in profondità, con la regola depth first, oppure in qualità, con la regola

best first), ed il tipo di rilassamento effettuato per il calcolo del lower bound

(oltre al rilassamento continuo descritto, si può usare ad esempio il cosid-

detto rilassamento lagrangiano). Per un’analisi più approfondita relativa

all’applicazione di rilassamenti ad un problema di Network Design simile a

quello presentato in questa tesi si veda [6].

Per ulteriori informazioni sul Branch and Bound e sugli altri metodi per

la Programmazione Lineare Misto-Intera si veda [3], mentre per la presen-

tazione generale dei metodi matematici per la Programmazione Lineare si

può far riferimento a [4], oltre che allo stesso [3].

3.2 Euristiche basate su ricerca locale

Il metodo del Branch and Bound è un metodo esatto, ovvero dopo un numero

finito di passi determina la soluzione del problema, ammesso che essa esista.

L’inconveniente è che quando si ha a che fare con problemi PLMI, al crescere

delle dimensioni del problema, i tempi computazionali crescono esponenzial-

mente, e questo pone in effetti un notevole limite alla sua applicazione in

problemi di grandi dimensioni.

Assumendo allora di non riuscire a determinare la soluzione ottima in

un tempo accettabile, è auspicabile per lo meno riuscire a trovarne una il

più possibile prossima ad essa in un tempo relativamente breve, ed è in

questo ambito che si inquadrano le procedure euristiche. Un’euristica vuole

dunque essere un metodo veloce per risolvere un problema di ottimizzazione

combinatiorica, senza la garanzia di raggiungere il vero e proprio ottimo. Le

euristiche si suddividono in euristiche costruttive polinomiali ed euristiche

14

basate su ricerca locale. Le prime cercano di “costruire” in modo progressivo

soluzioni “buone” facendo ad ogni passo una scelta a caso fra le migliori k

possibili. Quelle basate sulla ricerca locale si propongono invece di costruire

un “intorno” di una soluzione al fine di ricercare al suo interno una soluzione

migliore. Ci concentriamo su questo secondo tipo di euristiche, perché è qui

che si inquadra il metodo del Local Branching.

Chiamiamo X lo spazio delle soluzioni ammissibili del problema, e sup-

poniamo di poter determinare una soluzione ammissibile qualsiasi x ∈ X.

1

Occorre allora definire un vicinato di x , ovvero un insieme V (x ) ⊂ X che

1 1

sia sufficientemente piccolo da poter essere esplorato proficuamente. Si cerca

quindi di trovare una soluzione x ∈ V (x ) migliore di x , e poi si reitera il

2 1 1

processo costruendo un secondo intorno V (x ) e cercando lı̀ una soluzione

2

ancora migliore, e cosı̀ via...

Possiamo riassumere l’algoritmo nei seguenti passi:

Inizializzazione: si sceglie una soluzione iniziale ammissibile x come

1. 1

soluzione corrente e si calcola il valore della sua funzione obiettivo

Generazione del vicinato: si seleziona un vicinato V (x ) della soluzione

2. i

corrente x

i