Capitolo 4 Sperimentazioni

Capitolo 4

Sperimentazioni

In questo capitolo viene descritto il dataset utilizzato per effettuare i test e il formato adottato per descrivere le istanze del problema; vengono inoltre riportati i criteri con cui sono state condotte le sperimentazioni e i risultati ottenuti con il software da noi prodot-to.

Il problema dei cammini bilanciati con la particolare funzione obiettivo studiata in que-sta tesi non è mai que-stato affrontato in letteratura e quindi non sono disponibili algoritmi né esatti né euristici con cui effettuare un confronto. Per poter valutare la qualità dei ri-sultati ottenuti in termini di valore della funzione obiettivo e di tempi di calcolo, si è quindi deciso di effettuare un confronto con CPLEX 9.1, risolutore commerciale per problemi di Programmazione Lineare Intera [20].

4.1 Descrizione del dataset

I grafi che abbiamo utilizzato per generare le istanze del problema dei cammini bilan-ciati sono grafi di istanze relative a problemi di progetto e routing di reti di telecomuni-cazioni disponibili presso i siti web [18] e [19].

Test set 1. Inizialmente l’approccio euristico è stato testato su un gruppo di ventinove

istanze generate nel seguente modo. Sono stati prelevati alcuni file appartenenti alla li-breria SNDlib e messi a disposizione dallo ZIB [18] contenenti la descrizione di pro-blemi di progetto di reti nell’ambito delle telecomunicazioni; di tali propro-blemi è stata uti-lizzata la descrizione della rete sottostante al problema stesso e il costo di routing, lad-dove presente, associato agli archi del grafo. A tale costo, inoltre, è stato sommato un intero tra uno e cinquanta generato in modo random. I nodi origine e destinazione sono stati generati sulla base della dimensione delle rispettive stelle entranti ed uscenti in numero pari a _⎡⎢log n_⎤⎥, dove n è il numero di nodi del grafo. In particolare, i primi sono

stati selezionati in ordine di cardinalità della stella entrante non decrescente, e i secondi in ordine di cardinalità della stella uscente non decrescente. Per ognuna di tali istanze, è stato risolto sia il caso in cui origini e destinazioni possono essere connessi in modo qualsiasi, sia il caso in cui origine e destinazioni devono essere collegate rispettando le coppie fornite in input. In quest’ultimo caso le coppie sono state definite nel seguente modo: la coppia i-esima è formata dall’ i-esima origine e dall’ i-esima destinazione. I costi degli archi delle istanze di questo primo insieme variano in [1,50] tranne per le due istanze atlanta e otn-ibcn-ibbt in cui variano, nel primo caso, in [80,115] e, nel se-condo caso, in [300,1400].

Nella tabella 1 sono riportati i dati relativi a questo primo insieme di istanze, dove #V e #E indicano rispettivamente il numero di nodi e il numero di archi del grafo e k indica il numero di coppie origini-destinazioni dell’istanza del problema.

nome #V #E k nome #V #E k atlanta 15 22 3 otn-ibcn-ibbt 37 57 5 dfn-bwin 10 45 3 pdh1 11 34 3 dfn-gwin 11 47 3 pdh2 11 34 3 di-yuan 11 42 3 pioro40 40 89 5 france 25 46 4 polka 12 18 3 italy 30 59 4 rome13 14 21 3 janos-eu 37 114 5 sdh1 18 33 4 janos-us 26 84 4 sun 27 102 4 janos-us-ca 39 122 5 ta1 24 55 4 newyork 16 49 4 ta2 65 108 6 nobel-eu 28 41 4 zib16 16 51 4 nobel-germany 17 26 4 zib17 17 31 4 nobel-us 14 21 3 zib28 28 41 4 norway 27 51 4 zib54 54 81 5 nsfnet 14 21 3 Tabella 1

Test set 2. L’approccio euristico è stato testato anche su un secondo gruppo di

cinquan-tadue istanze generate a partire da un ulteriore set di istanze di telecomunicazioni di-sponibili in [19] e descritte in [3]. In [3] si affronta il problema della progettazione di reti di telecomunicazioni a fibra ottica formulando tale problema come un problema di flusso multicommodity. Dai file contenenti la descrizione delle istanze è stata prelevata la struttura della rete, il costo di installazione associato agli archi e (con n nu-mero di nodi del grafo) coppie origine-destinazione tra quelle elencate nella sezione demand del file sorgente. Poiché nelle istanze descritte in [3] gli archi sono non ti, abbiamo duplicato ognuno di questi archi in modo da averne uno per ogni orienta-mento e abbiamo assegnato lo stesso costo ad entrambi. Le reti sottostanti a questo gruppo di istanze del problema dei cammini bilanciati sono dunque fortemente cicliche. Anche per questo secondo gruppo, per ogni istanza è stato risolto sia il caso in cui origi-ni e destinazioorigi-ni possono essere connesse in modo qualsiasi sia quello in cui devono es-sere connesse rispettando le coppie date in input.

log n

⎢⎣ ⎥⎦

Le istanze di questo test set possono essere divise nei seguenti gruppi in base all’intervallo di variabilità dei costi e alla differenza tra l’arco di costo massimo e l’arco di costo minimo. Un primo gruppo contiene tutte le istanze del tipo net* e del tipo bhv*; in tali istanze i costi degli archi sono contenuti nell’intervallo [10,600] e la differenza tra il costo minimo e il costo massimo degli archi è (tranne per bhv1c, bhvac e bhvbc) circa 500. In bhv1c, bhvac e bhvbc la differenza in costo tra l’arco più costoso e l’arco meno costoso è circa 300 e i costi degli archi appartengono all’intervallo [100,450]. Il secondo gruppo contiene le istanze cost239, eon* e pacbell* i cui costi degli archi ap-partengono all’intervallo [3,35] e la differenza tra l’arco di costo massimo e l’arco di costo minimo è circa 20. Le istanze del tipo latadl* e usld* costituiscono il terzo grup-po; i costi degli archi di tali istanze appartengono all’intervallo [6,65] e la differenza in costo tra l’arco di costo massimo e l’arco di costo minimo è circa 50. Le istanze nsf* costituiscono un gruppo in cui il minimo costo degli archi è 10 e il massimo costo è 160. I costi degli archi delle istanze arpanet_99 e njlata* variano in [10,95] con una dif-ferenza in costo tra l’arco più costoso e l’arco meno costoso di circa 70. Gli ultimi due gruppi sono costituiti, il primo, dalla singola istanza arpa2_99 e, il secondo, dalle istan-ze toronto*. Nell’istanza arpa2_99 il costo minimo degli archi è 3 e il costo massimo è

19; nelle istanze toronto* il costo di un arco di costo minimo è 2 e il costo di un arco di costo massimo è 9.

Nella Tabella 2 sono riportati i dati relativi alle istanze contenute nel secondo test set.

nome #V #E k nome #V #E k arpa2_99 21 52 4 net_20_5 20 96 4 arpanet_99 24 100 4 net_20_20 20 100 4 bhv1c 14 38 3 net_20_60 20 92 4 bhv2c 24 56 4 net_20_99 20 98 4 bhv3c 29 124 4 net_25_5 25 118 4 bhv4c 18 60 4 net_25_20 25 116 4 bhv5c 19 54 4 net_25_60 25 124 4 bhv6c 27 78 4 net_25_99 25 124 4 bhv7c 23 66 4 net_30_5 30 142 4 bhv8c 28 70 4 net_30_20 30 142 4 bhv9c 24 86 4 net_30_60 30 146 4 bhvac 19 46 4 net_30_99 30 146 4 bhvbc 14 36 3 njlata_5 11 46 3 bhvcc 27 78 4 njlata_25 11 46 3 bhvdc 29 72 4 njlata_99 11 46 3 bhvec 20 54 4 nsf1a 14 42 3 cost239 11 44 3 nsf1b 14 42 3 eon_5 19 74 4 nsf2 14 44 3 eon_25 19 74 4 pacbell_25 15 42 3 latadl_5 39 172 5 pacbell_99 15 42 3 latadl_25 39 172 5 toronto_5 25 110 4 latadl_99 39 172 5 toronto_25 25 110 4 net_15_5 15 74 3 toronto_99 25 110 4 net_15_20 15 70 3 usld_5 28 90 4 net_15_60 15 74 3 usld_25 28 90 4 net_15_99 15 64 3 usld_99 28 90 4 Tabella 2

4.2 Descrizione di una singola istanza

Nel software implementato si assume che la descrizione di un’istanza del problema dei cammini bilanciati sia contenuta in un file di testo con il seguente formato.

Tutte le informazioni necessarie alla descrizione del problema devono essere distribuite su k+6 linee nel seguente modo:

• la prima linea contiene il numero di nodi del grafo seguito dal numero di archi e dal numero di coppie origine-destinazione;

• la seconda linea contiene la coda degli archi del grafo; l’i-esimo elemento di questa riga è quindi la coda dell’i-esimo arco del grafo;

• la terza linea contiene la testa degli archi del grafo; quindi l’i-esimo elemento indica la testa dell’i-esimo arco del grafo;

• nella quarta e quinta linea sono riportati, rispettivamente, i k nodi sorgente e i k nodi destinazione; qualora si voglia risolvere un’istanza in cui siano date coppie di nodi origindestinazione, l’i-esimo elemento della quarta riga e l’i-esimo e-lemento della quinta riga indicano, rispettivamente, l’origine e la destinazione dell’i-esima coppia;

• in ognuna delle k righe successive sono riportati i costi degli archi del grafo da utilizzare per ogni coppia origine-destinazione; le k righe devono essere tutte uguali qualora si stia considerando un’istanza in cui origini e destinazioni non sono accoppiate, possono invece essere diverse tra loro qualora si consideri il caso di coppie date. In questo secondo caso, dunque, il cammino che unisce la i-esima origine alla i-i-esima destinazione sarà cercato sul grafo i cui costi degli ar-chi sono riportati nella riga i+5 del file di testo. Inoltre, se per la coppia i-esima l’arco j non esiste, basta imporre che per la coppia i tale arco abbia costo infinito (INT_MAX);

• l’ultima riga contiene la stringa false o la stringa true per indicare se i nodi ori-gine e destinazione possono essere connessi in modo qualsiasi o se ogni oriori-gine deve essere connessa alla propria destinazione, rispettivamente.

4.3 Parametri delle sperimentazioni

Come descritto nel paragrafo 2.2, l’approccio euristico da noi progettato e realizzato si basa sulla scelta del numero di colori da utilizzare per colorare i nodi del grafo e sul numero di colorazioni con cui effettuare la ricerca dei cammini bilanciati node-disjoint.

I valori scelti per questi due parametri per effettuare le sperimentazioni sono: • numero di colori pari al 70% e all’ 80% della cardinalità dei nodi del grafo. • numero di colorazioni pari a 5, 10, 15, 20, 25 e 30.

Nella fase di sperimentazione, quindi, per ogni istanza, sono state testate tutte le combi-nazioni dei valori dei due parametri sopra elencati.

Su ogni istanza è stata testata anche la versione esatta dell’approccio euristico, che si ot-tiene colorando tutti i nodi del grafo con colori distinti. La soluzione ottima del proble-ma può essere infatti ottenuta dando in input all’euristica la seguente combinazione dei due parametri (numero colori, numero colorazioni): (100% , 1).

Ognuna delle precedenti combinazioni è stata testata sia con la versione “con time limit di un’ora” in cui, ricordiamo, si impone un limite di un’ora alla ricerca dei cammini bi-lanciati, sia con la versione “con blocchi di cinque minuti” dell’approccio euristico in cui si permette che trascorrano al più cinque minuti tra due miglioramenti successivi della funzione obiettivo e in cui, trascorsi cinque minuti senza che sia stato effettuato alcun miglioramento, viene interrotta la ricerca binaria nell’intervallo corrente per farla riprendere nell’intervallo destro. Le due versioni sono descritte in dettaglio in 2.2.2. La versione “con scaling dei costi”, descritta in 2.2.2, è stata testata a partire dalla ver-sione esatta dell’approccio euristico e con l’impostazione del limite di tempo di un’ora. Si ricorda che in tale versione, fissato un parametro ε>0, si effettua la ricerca dei cam-mini bilanciati sostituendo il costo dell’arco c_ij

( )

max ij c V c ε ⎡ # ⎤ × ⎢ ⎥ ⎢ ⎥, arco del

grafo, e, terminata la ricerca, si considerano i cammini generati e se ne calcola il costo rispetto ai costi originali, valutando la differenza in costo tra il cammino più costoso e quello meno costoso.

(

Nella fase di sperimentazione, per tutte le istanze, sono stati testati i valori di ε apparte-nenti a 1,1,3 2 2 ⎧ ⎨ ⎩ ⎭ ⎫

⎬ ; per alcune istanze di entrambi i test set, sono stati valutati anche i ri-sultati ottenuti effettuando lo scaling dei costi con i valori di ε appartenenti a

5 2, ,3,10 2 ⎧ ⎨ ⎩ ⎭ ⎫

⎬ . Si è deciso di valutare questi ulteriori valori di ε in quanto i primi valori testati non hanno generato una significativa riduzione del grafo espanso.

Tutte le sperimentazioni sono state effettuate su un computer con doppio processore AMD Opteron 246 2 GHz , 2 GB di RAM e sistema operativo Linux, kernel 2.6.13-1. Il software è stato scritto in C++ e compilato con GNU gcc 4.0.1.

4.4 Analisi del comportamento dell’approccio euristico

Le prime osservazioni da fare riguardano il tempo richiesto per verificare l’equivalenza di due colorazioni e l’occupazione di memoria dovuta alla gestione delle colorazioni. In tutte le istanze e in tutte le versioni del software testate, la generazione delle colora-zioni e la verifica dell’equivalenza sono operacolora-zioni che hanno richiesto una percentuale minima del tempo totale richiesto dall’approccio euristico. Per dare un’idea dell’ordine di grandezza, le due operazioni sono sempre state effettuate in meno di un centesimo di secondo. Si è quindi deciso di implementare nel software il controllo sull’equivalenza tra le colorazioni ed evitare quindi che l’euristica effettui iterazioni “inutili” utilizzando colorazioni equivalenti ad altre precedentemente testate.

Per quanto riguarda l’occupazione di memoria richiesta dalle strutture dati necessarie alla descrizione delle colorazioni e al controllo dell’equivalenza (descritte nel paragrafo 3.4.4), in nessuna delle istanze testate tale occupazione di memoria è mai risultata one-rosa. Non è stato quindi necessario applicare alcun algoritmo di compressione agli ele-menti degli insiemi V j

[ ]

4.5 Analisi dei risultati

Analizziamo ora la qualità delle soluzioni trovate e i tempi richiesti dalle diverse ver-sioni dell’approccio euristico. Nelle Appendici A e B sono riportate le tabelle che con-tengono, rispettivamente, i risultati ottenuti relativamente al test set 1 e relativamente al test set 2. Risultati riassuntivi, che sintetizzano gli esiti principali della sperimentazione, sono invece riportati nelle tabelle A e B. Nelle tabelle A e B i risultati sono riportati de-dicando una colonna ad ogni istanza, mentre nelle appendici A e B per ogni istanza è stata riportata una tabella contenente tutti i risultati ottenuti.

La prima informazione riportata è il nome dell’istanza con suffisso “False” o “True” ad indicare, rispettivamente, se si è risolto il caso in cui i nodi origine e i nodi destinazione possono essere connessi in modo qualsiasi o se devono essere connessi rispettando le coppie fornite in input.

La cella approxU, presente solo nelle tabelle delle appendici, contiene la prima appros-simazione del valore di U ottenuta come descritto in 2.1, cioè: approxU =

. Nella cella U è riportata invece la stima ottenuta mediante , come descritto nel paragrafo 3.4.1.

(

)

max min

c

α −

Nelle celle mcf (per il caso di coppie origine-destinazione non date) ed sptree (per il ca-so di coppie date) è riportato il valore della prima ca-soluzione ammissibile calcolato, co-me descritto in 3.4.2 e 3.4.3, tramite la risoluzione di un problema di flusso di costo mi-nimo o il calcolo di cammini minimi rispettivamente. Il calcolo dei cammini minimi non ha restituito alcuna soluzione ammissibile per una sola istanza del primo test set e in tre del secondo. In tutti gli altri casi entrambe le tecniche hanno restituito ottimi risul-tati che hanno permesso di ridurre l’estremo superiore dell’intervallo iniziale della ri-cerca binaria almeno della metà. Sono molti i casi in cui la riduzione è risultata essere 1/10 oppure 1/20 di U o ancora maggiore, come ad esempio per l’istanza usld_99 del secondo test set in cui il valore restituito dall’euristica iniziale è circa U/150. In entram-bi i casi, l’esecuzione dell’euristica iniziale è sempre stata estremamente rapida (in me-dia 0,01 secondi).

Nelle tabelle riassuntive seguono dieci “coppie di righe”. Ogni coppia è dedicata a con-tenere i risultati ottenuti con la versione esatta dell’approccio euristico (numero di colori

pari al 100% della cardinalità dei nodi del grafo) combinata con una delle tre varianti dell’approccio implementate e descritte in 2.2.2. L’ultima coppia contiene i risultati ot-tenuti con CPLEX. In ogni coppia la prima riga contiene il valore della soluzione trova-ta e la seconda il tempo impiegato a calcolarlo.

Nelle appendici A e B, per le versioni “con time limit di un’ora” e “con blocchi di cin-que minuti”, sono riportati anche i risultati ottenuti con tutte le combinazioni dei para-metri di input (numero colori, numero colorazioni) specificati in 4.3. I valori dei due pa-rametri sono riportati nelle colonne indicate rispettivamente con –N e –M. I risultati ot-tenuti con la versione esatta dell’euristica e limite di tempo di un’ora sono riportati nella cella ottima e nelle celle indicate con sono riportati il numero di archi di cui è costi-tuito l’i-esimo cammino calcolato. Nelle appendici, per ogni istanza, sono riportate an-che informazioni come il numero di nodi del grafo (cella nodes), il numero di archi (cel-la arcs) e il numero di coppie di nodi origine-destinazione (cel(cel-la comm).

i

k

Versione “con time limit di un’ora” e versione “con blocchi di cinque minuti”

Sia nel test set 1 che nel test set 2, le istanze possono essere divise in prima approssima-zione in due categorie:

1. quelle in cui U << approxU. 2. quelle in cui U ~ approxU.

Per tutte le istanze della prima categoria, la versione esatta dell’approccio euristico, quella cioè in cui viene assegnato un colore distinto ad ogni nodo del grafo, trova la so-luzione ottima molto rapidamente, in tempi solitamente assai minori o equivalenti a quelli richiesti dal solutore commerciale CPLEX. Il lettore tenga anche in conto, soprat-tutto per quei casi in cui il tempo totale dell’euristica corrisponde a pochi centesimi di secondo, che mentre CPLEX genera un output di una sola riga, il nostro software genera file di log molto estesi per poter analizzarne il comportamento, e che nel tempo totale riportato è incluso anche il tempo richiesto per la generazione dell’output. Rientrano in questa categoria le istanze atlanta e nobel-germany per il primo insieme di istanze, e ar-pa2_99 per il secondo test set. Come si può osservare dai risultati riportati nelle due Appendici, per tutte le istanze della prima categoria conviene utilizzare la versione esat-ta dell’approccio euristico piuttosto che le versioni approssimate, che utilizzano un

nu-mero di colori minore del nunu-mero dei nodi del grafo (colorazione dei nodi pari al 70% oppure 80% della cardinalità dei nodi del grafo).

Per le istanze di questa prima categoria, quindi, l’approccio proposto è sempre in grado di calcolare molto velocemente una soluzione ottima in tempo inferiore al tempo richie-sto dal software commerciale CPLEX.

In questo caso il confronto con CPLEX è equo poiché stiamo valutando la versione ot-tima dell’euristica e la risoluzione otot-tima del modello di P.L.I. imponendo anche a CPLEX un time limit pari ad un’ora. Non sarebbe invece molto corretto confrontare i tempi dell’euristica (colorazione dei nodi colorazione dei nodi pari al 70% o all’80% della cardinalità dei nodi del grafo e versione “con blocchi di cinque minuti”) con CPLEX.

Le istanze della seconda categoria, quelle cioè per cui U ~ approxU, possono essere ul-teriormente suddivise in due sottoinsiemi: quelle in cui il numero di nodi del grafo e-spanso è dell’ordine di n×U e quelle in cui, invece, tale numero è molto minore di n×U, dove n denota il numero di nodi del grafo di input. Rientrano in questo secondo caso, ad esempio, dfn-gwin per il primo gruppo di istanze e arpanet_99 e bhv1c per il secondo. Anche su questo gruppo di istanze la versione esatta dell’approccio euristico risulta es-sere quasi sempre migliore di CPLEX o equivalente. La soluzione ottima è infatti de-terminata molto rapidamente, spesso in tempi assai inferiori a quelli richiesti dal softwa-re commerciale CPLEX.

Le istanze in cui U ~ approxU e in cui il grafo espanso ha un numero di nodi pari a cir-ca n×U sono le istanze che sono risultate essere più critiche per le versioni dell’approccio euristico in fase di analisi. Esempi di queste istanze sono janos-eu e ja-nos-us per il primo test set, e bhv2c e bhvdc per il secondo. Ciò che probabilmente ac-cade è che nel grafo espanso sono presenti circa U copie di ogni nodo. Questo comporta che, nella ricerca binaria, il numero di sottografi da analizzare per ogni valore di

[

]

δ∈ è dell’ordine di U, che in tali casi è un valore molto elevato. Il tempo richie-sto per calcolare la soluzione ottima, quindi, è tanto maggiore quanto più sono i valori di δ da analizzare prima del valore di δ corrispondente alla soluzione ottima e quanto più sono grandi le dimensioni del grafo espanso G_U corrispondente; questo accade, ad

esempio, sia per l’istanza janos-eu che per l’istanza janos-us. Facciamo notare al lettore che per queste istanze l’euristica iniziale trova una buona soluzione molto velocemente (in al più un centesimo di secondo). In particolare per l’istanza janos-us (caso di coppie non date) la soluzione trovata, in tempo molto rapido, dall’euristica iniziale è una solu-zione ottima e l’operasolu-zione che richiede molto tempo è la certificasolu-zione dell’ottimalità della soluzione trovata.

In questo gruppo di istanze rientrano anche casi, come janos-us-ca e sun nel primo gruppo e toronto_5 nel secondo, che risultano essere “difficili” anche per CPLEX e su cui il nostro software ha prestazioni notevolmente migliori. Per queste istanze il nostro software o ottiene soluzioni migliori di quelle trovate da CPLEX impiegando lo stesso tempo impiegato da CPLEX o trova le stesse soluzioni trovate da CPLEX ma in tempi notevolmente minori.

Ci sono alcuni casi, come bhv4c nel secondo test set, in cui U ~ approxU, il grafo e-spanso ha un numero di nodi molto elevato, circa (n×U)/2, ma il numero di sottografi da analizzare per ogni valore di δ della ricerca binaria è molto minore di U . Tali istanze, dunque, risultano di facile risoluzione per il nostro software. In particolare, per bhv4c il massimo numero di sottografi da analizzare per i valori di δ incontrati nella ricerca bi-naria è stato tre.

Su tutte le istanze critiche generalmente la versione del software “con blocchi di cinque minuti” ottiene, con le versioni approssimate dell’euristica (numero di colori pari al 70% o 80% del numero di nodi), risultati assai migliori di quelli ottenuti con la versione “con time limit di un’ora”.

Si noti, inoltre, che il secondo dataset contiene diverse istanze che risultano estrema-mente difficili o solo per le versioni in esame dell’approccio euristico o per CPLEX. Ad esempio, tutte le istanze del tipo latadl* sono estremamente critiche per CPLEX ma non per il nostro software che risolve le istanze in pochi secondi; accade invece il contrario per le istanze net_20_20 e net_20_60. In particolare, nel secondo test set, ci sono tre i-stanze per cui CPLEX non trova alcuna soluzione mentre l’approccio euristico proposto individua una soluzione ottima in tempi rapidissimi.

Versione “con scaling dei costi”

Tale versione dell’approccio euristico è stata ideata per ridurre le dimensioni del grafo espanso e ridurre, di conseguenza, i tempi necessari per la ricerca dei cammini bilancia-ti. In alcuni casi, i valori di ε stabiliti inizialmente ( 1/2, 1 e 3/2) non hanno generato una significativa riduzione del grafo espanso; ciò è accaduto a causa del rapporto tra i costi degli archi, il numero di nodi del grafo di tali istanze e i valori di ε scelti. In alcune di queste istanze e per alcuni valori di ε, si ha addirittura che max

V c

ε # _>

e quindi, nello scaling dei costi, il costo degli archi di costo e la dimensione del grafo espanso non si riducono ma bensì aumentano. Per tale motivo, per queste istanze è stato speri-mentato uno scaling dei costi più accentuato considerando anche per i valori di ε appar-tenenti a max c 5 2, ,3,10 2 ⎧ ⎫ ⎨ ⎬ ⎩ ⎭. I valori di ε appartenenti a 2, ,3,105 2 ⎧ ⎫ ⎨ ⎬

⎩ ⎭ sono stati testati anche per quei casi in cui, per ottenere buoni risultati in tempi che fossero competitivi con quelli di CPLEX, è stato necessaria una maggiore “compressione” del grafo espanso.

La prima osservazione da fare è che, per la maggior parte delle istanze, le versioni dell’approccio euristico basate su scaling dei costi sono drasticamente più rapide delle versioni “con time limit di un’ora” e “con blocchi di cinque minuti”, e producono quasi sempre una soluzione ottima o una buona soluzione.

Altre osservazioni su questa versione dell’approccio euristico sono le seguenti:

• i tempi impiegati per calcolare una soluzione con la versione dell’approccio eu-ristico in esame diminuiscono all’aumentare del valore del parametro ε.

• all’aumentare di ε aumenta anche l’errore commesso nel calcolo della soluzione ma, nell’esperienza computazionale condotta, per quasi tutte le istanze si sono ottenute comunque soluzioni di buona qualità.

• nel primo test set, per 54 casi su 58 esiste un valore di ε in corrispondenza del quale con il nostro software si ottiene la soluzione ottima in tempi minori o u-guali a CPLEX; in due dei casi rimanenti la versione esatta dell’approccio euri-stico senza scaling dei costi calcola la soluzione ottima in tempi decisamente

minori di CPLEX. Nel test set 2 un tale valore di ε esiste per 89 casi su 104; per i restanti casi, in corrispondenza del valore di ε per il quale si calcola una solu-zione più rapidamente di CPLEX, si ottiene comunque una buona solusolu-zione. La versione “con scaling dei costi” si è dunque rivelata molto efficiente non solo per trovare e certificare più rapidamente delle altre versioni soluzioni ottime, ma anche co-me efficace struco-mento per la generazione di buone e molteplici soluzioni ammissibili. L’idea di scalare i costi, quindi, è risultata molto efficace ed incisiva sul piano delle spe-rimentazioni.