Questo progetto focalizza l'attenzione sui problemi di ottimizzazione dinamica, risolti attraverso l'algoritmo per DPOP,
di cui si può trovare il paper di riferimento a questo indirizzo.
Le
istanze dei problemi in input devono essere nel formato standard
utilizzato dal risolutore "concorrente" ADOPT; esempi di queste istanze
possono essere reperiti a questo indirizzo.
Il risolutore per DPOP da costruire deve essere implementato in Java.
I problemi che il risolutore deve essere in grado di manipolare sono problemi di ottimizzazione, in cui l’input sarà caratterizzato da variabili ciascuna con il suo dominio di valori, e dai vincoli sulle variabili. L’algoritmo per DPOP in particolare risolve problemi di massimizzazione con soli vincoli binari, dato che è possibile ridurre qualsiasi problema di ottimizzazione in questa versione. Questo progetto, in particolare, si focalizza sulla risoluzione di un sottoinsieme dei problemi di massimizzazione, vale a dire su problemi di massimizzazione del numero di vincoli soddisfatti (Max CSP). Il concetto di agente, di cui si fa menzione nel paper del DPOP, in questo progetto collassa sul concetto di variabile: in altre parole ogni agente detiene una e una sola variabile.
Riassumendo la sequenza delle operazioni che sarà svolta dal risolutore per DPOP: viene letto in input un file di descrizione contenente l’elenco delle variabili, il loro dominio, e i vincoli binari a cui tali variabili sono sottoposte. I vincoli saranno descritti con NOGOOD, vale a dire saranno specificate solamente le coppie di valori non ammesse per le variabili del vincolo; questa descrizione può essere facilmente trasformata per risolvere Max CSP, impostando i vincoli in maniera tale che le coppie di valori non consentite abbiano peso −1 e quelle consentite 0. Il parsing dell’input genera un grafo non diretto, e successivamente tramite un’opportuna visita DFS viene generato lo pseudo-tree, vale a dire la struttura dati su cui si basa l’algoritmo DPOP. Una volta ottenuto lo pseudo-tree, la computazione si svolge visitando dapprima dal basso verso l’alto l’albero nella sua interezza (util propagation) e poi dall’alto verso il basso (value propagation). A questo punto la soluzione è disponibile: se il risultato è 0 nessun vincolo è stato violato, altrimenti un qualsiasi valore negativo rappresenta la violazione di uno o più vincoli. Per rendere la soluzione più completa, durante la computazione vengono memorizzati i vincoli violati, in modo da poterli visualizzare al termine della computazione stessa.
Relazione del progetto in formato pdf: relazione
Sorgenti Java del progetto: codice
Librerie JGraph5 utilizzate: JGraph5