Determinazione del vincitore in un'asta combinatoriale
- Autori: Federica Zampedri e Sara Sogari
- Progetto del corso di: Ragionamento Automatico
- Anno Accademico: 2009/2010
- Docente: Alessandro Farinelli
Algoritmo
Tale progetto si pone l'obiettivo di implementare e valutare un
algoritmo completo per risolvere il problema di determinazione del
vincitore in un'asta combinatoriale attraverso l'approccio della Bucket
Elimination. Un'asta combinatoriale è usata quando si vogliono vendere
più oggetti contemporaneamente; gli offerenti possono sottoporre
un'offerta su un sottoinsieme di beni. Ogni offerta sarà quindi
rappresentata da:
- un sottoinsieme di beni
- il valore dell'offerta
Le offerte vincenti verranno scelte in modo da perseguire uno
specifico obiettivo (nel nostro caso la massimizzazione del guadagno) e
in maniera
tale che ogni sottoinsieme assegnato sia disgiunto. Con tale programma
si è quindi cercato di simulare uno scenario simile a quello descritto
sopra, dove a fronte di un'insieme di proposte, verrà determinato il
sottoinsieme ottimale di offerte disgiunte.
Elenco delle classi
- Bid.java: classe contenente le proprietà e i metodi dell'oggetto offerta;
- Bucket.java:
classe che rappresenta il bucket vero e proprio; contiene l'insieme
delle relazioni presenti nel bucket e i metodi necessari a processarlo
e massimizzare la funzione costo;
- BucketElimination.java: classe principale in cui si
creano le offerte, si assegnano i vincoli ai bucket corrispondenti, si
massimizzano le funzioni costo e si propagano i valori per calcolare la
combinazione di offerte che ottimizza il guadagno;
- Relazione.java: rappresenta il vincolo fra due
offerte distinte, contiene tutte le possibili combinazioni valide che
le variabili (offerte) in questione possono assumere;
- SavitchIn.java: classe Java usata per l'input da tastiera.
Input
In ingresso il programma prende un insieme di offerte ognuna consistente di un insieme di oggetti e di un prezzo associato.
L'istanza viene passata al programma tramite un file .txt in cui si elencano tutte le offerte e i relativi costi.
Esempio:
85 1 3 12 18 6
66 8 7 16 9 3
dove ogni riga rappresenta un'offerta, il primo valore identifica il
prezzo e i restanti numeri costituiscono il sottoinsieme degli oggetti.
Link