Determinazione del vincitore nelle aste combinatorie: un approccio a vincoli
Autore
Alessio Guerri - Università degli Studi di Bologna - [2001-02]
Documenti
Abstract
La rapida evoluzione del commercio elettronico permette alle società di ampliare il proprio bacino d’utenza e le proprie potenzialità, eliminando le tipiche barriere che il commercio classico impone. In questo scenario, le aste combinatorie si inseriscono come metodo per superare le limitazioni intrinseche delle aste classiche, in cui è possibile piazzare un bene alla volta, decidendo il vincitore soltanto in base al prezzo offerto.
I beni che è possibile vendere tramite un’asta combinatoria possono essere di varia natura. In questa tesi saranno prese in considerazione aste combinatorie su insiemi coordinati di attività, attività, cioè, che devono essere svolte in accordo con determinati vincoli temporali, sia per quanto riguarda l’esecuzione dell’attività stessa, sia rispettando delle relazioni di precedenza tra due o più di esse.
I vantaggi ottenuti utilizzando tali aste sono indubbi, sia per chi vende sia per chi compra; tuttavia, l’introduzione di vincoli temporali e la possibilità di fare offerte su più oggetti contemporaneamente, rende estremamente più complicata la risoluzione del problema della determinazione del vincitore, intesa come ricerca della combinazione di offerte che riesce ad eseguire tutte le attività al minor prezzo possibile.
Il lavoro svolto nella seguente tesi intende risolvere tale problema tramite un approccio a vincoli, utilizzando algoritmi di ricerca incompleti, per ottenere risultati migliori sia in termini temporali sia in termini di ottimalità rispetto a quelli raggiungibili con altri sistemi esistenti.
Nel primo capitolo verranno introdotte le caratteristiche delle tecniche di soddisfacimento di vincoli, descrivendo gli algoritmi di esplorazione dello spazio di ricerca e i metodi utilizzati per guidare tale ricerca verso strade che più probabilmente portano ad una buona soluzione.
Nel secondo capitolo saranno introdotti i migliori algoritmi di ricerca incompleti reperibili in letteratura. Un algoritmo incompleto è un algoritmo che tenta di risolvere un problema eliminando alcune porzioni dello spazio di ricerca che, verosimilmente, non possono contenere una soluzione.
Nel terzo capitolo sarà introdotta la programmazione logica a vincoli sottolineando come, tramite questo paradigma, vengono superate le limitazioni tipiche della programmazione logica.
Nel quarto capitolo verranno descritte più formalmente le caratteristiche di un’asta combinatoria su insiemi coordinati di attività, specificando, in particolare, tutti i vincoli che dovranno essere soddisfatti da una qualsiasi soluzione.
Nel quinto capitolo sarà introdotta la libreria ILOG Solver, un insieme di metodi e funzioni utili per risolvere problemi di programmazione, allocazione, ottimizzazione, gestione delle risorse e simili, sfruttando la programmazione a vincoli. In particolare l’attenzione verrà focalizzata sulle funzioni effettivamente utilizzate nella tesi.
Nel sesto capitolo sarà descritto nel dettaglio il sistema software progettato e i metodi di generazione di problemi di aste combinatorie. Verrà introdotto MAGNET, un sistema per la generazione e risoluzione dei problemi che la presente tesi intende risolvere.
Nel settimo ed ultimo capitolo saranno presentati e discussi i risultati ottenuti dal sistema progettato. I risultati saranno inoltre paragonati con quelli ottenuti da MAGNET, al fine di verificare se l’approccio a vincoli possa rappresentare una valida alternativa ai metodi di risoluzione esistenti.
I beni che è possibile vendere tramite un’asta combinatoria possono essere di varia natura. In questa tesi saranno prese in considerazione aste combinatorie su insiemi coordinati di attività, attività, cioè, che devono essere svolte in accordo con determinati vincoli temporali, sia per quanto riguarda l’esecuzione dell’attività stessa, sia rispettando delle relazioni di precedenza tra due o più di esse.
I vantaggi ottenuti utilizzando tali aste sono indubbi, sia per chi vende sia per chi compra; tuttavia, l’introduzione di vincoli temporali e la possibilità di fare offerte su più oggetti contemporaneamente, rende estremamente più complicata la risoluzione del problema della determinazione del vincitore, intesa come ricerca della combinazione di offerte che riesce ad eseguire tutte le attività al minor prezzo possibile.
Il lavoro svolto nella seguente tesi intende risolvere tale problema tramite un approccio a vincoli, utilizzando algoritmi di ricerca incompleti, per ottenere risultati migliori sia in termini temporali sia in termini di ottimalità rispetto a quelli raggiungibili con altri sistemi esistenti.
Nel primo capitolo verranno introdotte le caratteristiche delle tecniche di soddisfacimento di vincoli, descrivendo gli algoritmi di esplorazione dello spazio di ricerca e i metodi utilizzati per guidare tale ricerca verso strade che più probabilmente portano ad una buona soluzione.
Nel secondo capitolo saranno introdotti i migliori algoritmi di ricerca incompleti reperibili in letteratura. Un algoritmo incompleto è un algoritmo che tenta di risolvere un problema eliminando alcune porzioni dello spazio di ricerca che, verosimilmente, non possono contenere una soluzione.
Nel terzo capitolo sarà introdotta la programmazione logica a vincoli sottolineando come, tramite questo paradigma, vengono superate le limitazioni tipiche della programmazione logica.
Nel quarto capitolo verranno descritte più formalmente le caratteristiche di un’asta combinatoria su insiemi coordinati di attività, specificando, in particolare, tutti i vincoli che dovranno essere soddisfatti da una qualsiasi soluzione.
Nel quinto capitolo sarà introdotta la libreria ILOG Solver, un insieme di metodi e funzioni utili per risolvere problemi di programmazione, allocazione, ottimizzazione, gestione delle risorse e simili, sfruttando la programmazione a vincoli. In particolare l’attenzione verrà focalizzata sulle funzioni effettivamente utilizzate nella tesi.
Nel sesto capitolo sarà descritto nel dettaglio il sistema software progettato e i metodi di generazione di problemi di aste combinatorie. Verrà introdotto MAGNET, un sistema per la generazione e risoluzione dei problemi che la presente tesi intende risolvere.
Nel settimo ed ultimo capitolo saranno presentati e discussi i risultati ottenuti dal sistema progettato. I risultati saranno inoltre paragonati con quelli ottenuti da MAGNET, al fine di verificare se l’approccio a vincoli possa rappresentare una valida alternativa ai metodi di risoluzione esistenti.
Questa tesi è correlata alla categoria
segnala questa pagina ::.