Tesi: Laurea magistrale in Scienze e Tecnologie dell'Informazione

Algoritmi di programmazione matematica per il
Max Edge Weighted Clique problem with multiple choice constraints

Molti problemi rilevanti in ambito sceintifico e tecnologico possono essere descritti e risolti con successo utilizzando modelli basati su grafi.

Ad esempio, in biologia computazionale sorge frequentemente il problema conosciuto come side-chain placement problem che consiste nel trovare la conformazione lineare di una proteina, in cui l'energia di legame tra gli amminoacidi sia minima e che, al contempo, assicuri un'adeguata stabilità strutturale. In modo simile, nell'ambito della management science, per garantire l'interoperabilità dell'insieme di reparti di una grande impresa è necessario scegliere il protocollo di interazione che massimizzi l'efficienza complessiva. Anche nell'ambito del progetto di reti di telecomunicazione sorge spesso l'esigenza di disporre i nodi che compongono la dorsale in modo da minimizzare i tempi di latenza o massimizzare la banda passante.

Tutti questi problemi hanno una struttura comune, riconducibile alla ricerca di una clique di peso massimo in un grafo opportuno.
In questa tesi viene affrontato il Max Edge Weighted Clique problem with Multiple choice Constraints (MEWCMC) che, dati un grafo pesato sia sui vertici che sui lati, e una partizione dell'insieme dei vertici, consiste nell'individuare una clique di peso massimo selezionando un vertice per ogni classe della partizione.

Il MEWCMC è un problema di ottimizzazione su grafo molto generico e, come molti altri problemi simili è NP-difficile. Attualmente non sono noti algoritmi in grado di risolvere in tempo polinomiale questa classe di problemi: per ottenere metodi di risoluzione efficaci, è necessario studiare il roblema in modo approfondito. Nella tesi vengono proposti modelli matematici e algoritmi per la risoluzione esatta del problema, basati su tecniche di enumerazione implicita.
In particolare è stato dapprima costruito un modello di programmazione lineare intera, un modello con funzione obiettivo quadratica e uno di programmazione semidefinita ottenuto tramite riformulazione del modello quadratico. Un'analisi sperimentale ha evidenziato che i solutori commerciali, utilizzando questi modelli, sono in grado di risolvere solo istanze di dimensioni ridotte.
Quindi, per superare le limitazioni dei solutori generici è stato sviluppato e implementato un algoritmo euristico di Tabu Search, in grado di determinare delle soluzioni di buona qualità, in tempi molto rapidi.
Infine è stato studiato e implementato un algoritmo ad-hoc, che sfrutta euristiche e tecniche di rilassamento per esplorare efficientemente l'albero di decisione. Il primo ingrediente dell'algoritmo è un rilassamento che utilizza tecniche di programmazione semidefinita per ottenere una stima per eccesso del valore della soluzione ottima. Il secondo ingrediente è un bound che sfrutta unicamente le proprietà combinatorie del problema e pu&obrave; essere calcolato in modo molto efficiente. Tale bound è utilizzato anche per ridurre le dimensioni iniziali del problema, eliminando a priori soluzioni sub-ottime. Il terzo ingrediente è un insieme di politiche di branching volte a migliorare l'efficienza nell'esplorazione dell'albero di ricerca. L'ultimo ingrediente è un'euristica di rounding, che utilizza le soluzioni fornite dal rilassamento per individuare altre soluzioni ammissibili.
Poichè la tecnica di rilassamento gioca un ruolo cruciale nell'efficienza dell'algoritmo ad-hoc è stata dedicata particolare attenzione alla possibilità di introdurre vincoli aggiuntivi, in grado di migliorare il bound senza aumentare significativamente il carico computazionale.

L'implementazione ha richiesto lo sviluppo di codice specifico con l'integrazione di solutori esterni. Infatti, la valutazione del rilassamento basato su programmazione semidefinita richiede l'impiego di algoritmi specifici, fra cui il metodo del cammino centrale, la cui efficienza varia sensibilmente in funzione della scelta di alcuni parametri.
Le prestazioni degli algoritmi implementati sono state valutate tramite un'estesa campagna sperimentale. Questa ha evidenziato che l'impiego delle tecniche di programmazione semidefinita è particolarmente efficace: permette di ottenere bound duali stretti, riducendo così il tempo necessario all'enumerazione implicita.
I risultati ottenuti dall'algoritmo ad-hoc sono stati confrontati con quelli dal solutore commerciale ILOG Cplex 11.2 a cui è stato fornito in ingresso il modello lineare intero. L'algoritmo ad-hoc risolve istanze di dimensioni molto maggiori rispetto a Cplex, comportandosi meglio sia in termini di tempo di calcolo che in termini di qualità dei bound. E' stato inoltre possibile verificare che l'euristica di Tabu Search implementata, nella maggior parte delle istanze testate, riesce ad individuare la soluzione ottima in pochi secondi.
L'efficacia del rilassamento semidefinito suggerisce che altre tecniche di rilassamento, basate su programmazione conica, possano essere efficaci nella soluzione di MEWCMC così come di altri problemi che presentano una struttura simile.

[ Download tesi (1.2M) ]

[ Download presentazione (979K) ]

Tesi: Laurea triennale in Informatica

Un algoritmo di Tabu Search per il Maximum Diversity Problem

La tesi ha vinto il premio Camerini-Carraresi 2006, il riconoscimento che l'Associazione italiana di Ricerca Operativa (AIRO) assegna annualmente agli autori delle migliori tesi di laurea realizzate nelle università italiane nell'ambito della ricerca operativa.


Il Maximum Diversity Problem (MDP) consiste nella scelta di un numero dato di elementi da una popolazione di partenza, in modo da massimizzare la loro reciproca diversità. Il problema ricorre in una vasta gamma applicazioni, come la definizione di trattamenti medici, calendari d'esame, giurie, nonchè alla selezione di investimenti e al VLSI design.

Il Maximum Diversity Problem è NP-difficile. Di conseguenza, a meno che P=NP, non è possibile trovare un algoritmo efficiente per risolverlo all'ottimo, ma diviene necessario ricorrere ad un approccio di tipo approssimato. Gli algoritmi esatti, infatti, permettono di risolvere istanze di dimensioni molto inferiori a quelle richieste dalle applicazioni.

Dopo un'esaustiva analisi della letteratura, si presenta un algoritmo di Tabu Search, con alcune varianti, che risolve il MDP in modo approssimato. Le varianti prese in considerazione includono meccanismi come l'uso di liste tabù costanti e variabili, di criteri di aspirazione, di una memoria a breve e lungo termine.

Si valutano infine le prestazioni degli algoritmi implementati, confrontandoli gli uni rispetto agli altri, ma anche rispetto ai risultati riportati in letteratura. Questi si riferiscono principalmente ad algoritmi di tipo GRASP (Greedy Randomized Adaptive Search Procedure). Il confronto è stato effettuato su differenti categorie di istanze prese dalla letteratura e riguarda la qualità delle soluzioni determinate e l'efficienza computazionale.

[ Download (387K) ]

Ultima modifica: Sunday 08th 2012f April 2012 11:05:55 AM


Creative Commons License hacker emblem
Except where otherwise noted, this site is licensed under a
Creative Commons Attribution 2.5 License

© Yari Melzani (2006)