Determinazione del vincitore nelle aste combinatorie: un approccio a vincoli

INTRODUZIONE 
ix  
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. 
  
CAPITOLO 1 
 
  
 
 
 
PROBLEMI DI SODDISFACIMENTO 
DI VINCOLI  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
PROBLEMI DI SODDISFACIMENTO DI VINCOLI 
 
3 
1.1 Introduzione 
 
In questo capitolo saranno introdotti i Problemi di Soddisfacimento di 
Vincoli (Constraint Satisfaction Problems, CSP) e i Problemi di 
Ottimizzazione Combinatoria (Combinatorial Optimization Problems, 
COP), che rappresentano i tipici problemi analizzati e risolti dai 
linguaggi di Programmazione Logica a Vincoli (Constraint Logic 
Programming, CLP). 
 
1.2 Problemi di Soddisfacimento di Vincoli e 
Problemi di Ottimizzazione 
 
Un CSP pu  essere definito su un insieme finito di variabili 
(X
1
,X
2
, ,X
n
) i cui valori appartengono a domini di definizione 
(D
1
,D
2
, ,D
n
) che, per questa trattazione, verranno supposti finiti, e su 
un insieme di vincoli. Un vincolo c(X
i1
,X
i2
, ,X
ik
) tra k variabili Ł un 
sottoinsieme del prodotto cartesiano 
ikii
DDD ××× K
21
 che specifica i 
valori delle variabili tra loro compatibili. Tale sottoinsieme non deve 
essere esplicitamente definito, ma Ł rappresentato in termini di relazioni. 
Una soluzione ad un CSP prevede l assegnamento di un valore ad ogni 
variabile, in modo da soddisfare tutti i vincoli imposti. 
Un COP Ł un CSP cui viene aggiunto un obiettivo. Esso Ł quindi piø 
formalmente descrivibile come un CSP il cui scopo non sia solo quello di 
trovare una soluzione ammissibile, bens  la soluzione ottima secondo un 
certo criterio di valutazione. Dato un algoritmo generale in grado di 
risolvere qualsiasi CSP, Ł possibile utilizzarlo per risolvere qualsiasi 
COP semplicemente aggiungendo all insieme di variabili, domini e 
vincoli del CSP, un ulteriore variabile che rappresenti la funzione 
obiettivo. Ogni volta che viene trovata una soluzione, il risolutore 
impone il vincolo che ogni ulteriore soluzione abbia il valore della 
funzione obiettivo migliore. Quando il procedimento porta ad un 
fallimento, l ultima soluzione trovata Ł senz altro quella ottima.  
CAPITOLO 1 
 
4 
La maggior parte di questi problemi sono NP-difficili, sono cioŁ 
problemi per i quali non Ł ancora stata trovata, e probabilmente non 
esiste, un algoritmo in grado di trovare la soluzione in un tempo 
polinomiale nella dimensione del problema. 
 
1.3 Albero decisionale e strategie di esplorazione 
 
Qualunque tecnica di risoluzione di problemi NP-difficili fa uso, 
almeno concettualmente, di un albero decisionale. Per un CSP, l albero 
decisionale si pu  ottenere facendo corrispondere ad ogni livello 
l assegnamento di una variabile, secondo un ordine prestabilito, e ad 
ogni nodo la scelta del valore da assegnare alla variabile corrispondente 
al livello in cui in nodo stesso si trova. ¨ quindi evidente che ogni foglia 
dell albero rappresenta una diversa combinazione di valori assegnati alle 
variabili. Le foglie associate ad assegnamenti compatibili con tutti i 
vincoli del problema sono soluzioni del problema stesso. La ricerca di 
una soluzione Ł quindi equivalente all esplorazione dell albero 
decisionale associato al problema, al fine di trovare una foglia con un 
assegnamento compatibile con i vincoli imposti.  
Una metodologia di esplorazione dell albero pu  essere quella di 
generare un assegnamento e verificare a posteriori se sia compatibile con 
i vincoli dati. In caso negativo viene continuata la ricerca in 
backtracking, risalendo l albero in maniera cronologica fino ad arrivare 
al primo nodo che contenga strade ancora inesplorate, e ripetendo 
l algoritmo su tali strade. Tale algoritmo Ł chiamato Generate and Test. 
Un altro algoritmo, leggermente migliore di questo, Ł lo Standard 
Backtracking, in cui ad ogni assegnamento di una variabile viene 
controllata la compatibilit  di tutte le variabili correntemente assegnate 
con i vincoli, evitando in caso di incompatibilit  di percorrere 
ulteriormente una strada che porter  sicuramente ad un fallimento. 
Notando per  che, in un problema con v variabili, ognuna delle quali 
abbia un dominio di cardinalit  d, esistono d
v
 foglie, cioŁ d
v
 possibili 
PROBLEMI DI SODDISFACIMENTO DI VINCOLI 
 
5 
assegnamenti, si capisce che utilizzare i vincoli solo a posteriori sia una 
strada impraticabile per i CSP normalmente analizzati. Infatti per un 
semplice problema con 5 variabili e domini di cardinalit  10, esistono 10 
milioni di permutazioni dei valori, cioŁ 10 milioni di foglie nell albero 
decisionale. Oltretutto, essendo questo valore esponenziale nel numero 
delle variabili, gi  un problema con il doppio di variabili porta ad avere 
10 miliardi di possibili assegnamenti, con un incremento del tempo di 
computazione di un fattore 1000. 
 ¨ per  possibile utilizzare i vincoli in maniera piø intelligente 
riducendo a priori l albero di ricerca. Per esempio, nella successiva 
figura 1.1 Ł rappresentato l albero decisionale di un semplice problema 
di 3 variabili con domini (0,1) e vincoli X≠ Y,X≠ Z,Z≥ X.  
 
 
Fig. 1.1: Esempio di albero decisionale per un problema di tre variabili 
con domini di cardinalit  2 
 
Il Generate and Test risale 4 volte l albero in backtracking prima di 
trovare la soluzione (0,1,1), mentre lo Standard Backtracking soltanto 2 
volte. Utilizzando per  i vincoli subito dopo l assegnamento del valore 0 
ad X, si pu  eliminare a priori il valore 0 sia da Y sia da Z, in quanto 
incompatibili rispettivamente con il primo e con il secondo vincolo, ed 
arrivare alla soluzione senza eseguire nessun backtracking. 
 
CAPITOLO 1 
 
6 
1.3.1 Tecniche di Consistenza e Algoritmi di 
Propagazione 
 
Le Tecniche di Consistenza e gli Algoritmi di Propagazione sono 
metodi che cercano, utilizzando i vincoli in maniera attiva, di prevenire 
a priori i fallimenti anzichØ recuperare quelli gi  avvenuti. Pu , infatti, 
accadere che un assegnamento sbagliato nei primi livelli dell albero 
produca come effetto il fallimento della ricerca in quel ramo molto piø 
tardi, quindi molto in profondit  nell albero decisionale. Un algoritmo in 
grado di riconoscere subito questo tipo di errori evita la generazione 
inutile di un elevato numero di sottoalberi. Entrambi i metodi si 
occupano di utilizzare i vincoli il prima possibile per evitare inutili 
ricerche e, quindi, inutile spreco di tempo e di risorse. 
Le Tecniche di Consistenza sono meccanismi per propagare i vincoli 
prima di cominciare la ricerca, e quindi derivare un problema piø 
semplice, ma equivalente a quello originale completo. Viceversa i 
secondi si basano sulla propagazione dei vincoli per eliminare, durante 
la ricerca, quei valori dai domini delle variabili, e quindi quelle porzioni 
dell albero decisionale, che porterebbero, associati ai valori gi 
assegnati, ad un sicuro fallimento. Tipicamente in un CSP vengono 
applicate prima le Tecniche di Consistenza e successivamente gli 
Algoritmi di Propagazione.  
Una volta che non sia piø possibile applicare tali metodi, o si Ł giunti 
ad una soluzione o Ł necessario scegliere un valore da assegnare ad una 
delle variabili ancora libere.  
La figura 1.2 esemplifica la differenza tra utilizzo dei vincoli a priori 
e a posteriori. Utilizzando i vincoli a priori viene evitata la fase di test, 
riducendo quindi drasticamente il numero di backtracking. Infatti, ogni 
assegnamento generato dal metodo Generate and Test, ha, perlomeno a 
priori, la stessa probabilit  di essere una soluzione di tutti gli altri 
assegnamenti; viceversa, l eliminazione di valori incompatibili dai 
domini grazie alla propagazione dei vincoli, comporta anche un aumento 
PROBLEMI DI SODDISFACIMENTO DI VINCOLI 
 
7 
della probabilit  di successo degli assegnamenti generati utilizzando 
solo i valori rimanenti. 
 
 
Fig. 1.2: Utilizzo dei vincoli nell esplorazione dell albero decisionale 
 
Propagare i vincoli Ł in ogni caso un operazione complessa che 
richiede un certo tempo per essere eseguita. Occorre quindi utilizzare 
l algoritmo che, nel problema in questione, riesca a fornire il miglior 
trade-off tra il costo della strategia e i risultati ottenuti, in termini di 
riduzione di domini.  
Tra gli algoritmi di propagazione solitamente implementati troviamo il 
Forward Checking e il Look Ahead. Il primo, dopo ogni assegnamento, 
elimina i valori incompatibili con quello appena istanziato dai domini 
delle variabili non ancora istanziate. Se ad un certo punto della 
computazione uno o piø domini risultassero vuoti, il meccanismo fallisce 
subito e prova altri valori per le variabili gi  istanziate, evitando cos  di 
scendere in un ramo dell albero decisionale che porterebbe sicuramente 
al fallimento e, di conseguenza, al backtracking. L algoritmo Look 
Ahead prevede che ad ogni istanziazione venga eseguito il Forward 
Checking, e venga inoltre sviluppato il Look Ahead (sguardo in avanti) 
che controlla l esistenza, nei domini delle variabili ancora libere, di 
valori compatibili con i vincoli contenenti solo variabili non istanziate. 
In altre parole, si controlla se, a causa della riduzione effettuata dal 
Forward Checking, i valori rimasti nei domini delle variabili libere 
possano ancora portare, scendendo nell albero, ad una soluzione, o se 
siano viceversa destinati ad un sicuro fallimento. 
Contrariamente agli algoritmi di propagazione, che propagano i 
vincoli in seguito ad istanziazioni delle variabili coinvolte nel problema, 
CAPITOLO 1 
 
8 
le tecniche di consistenza riducono il problema originale eliminando dai 
domini delle variabili i valori che non possono comparire in alcuna 
soluzione.  
Tutte le tecniche di consistenza sono basate su una rappresentazione 
del problema come un grafo di vincoli. Gli archi possono essere orientati 
o no: per esempio il vincolo > Ł rappresentato da un arco orientato, 
mentre il vincolo ≠ da uno semplice (non orientato o doppiamente 
orientato). 
Per ogni CSP, esiste un grafo in cui i nodi rappresentano le variabili, e 
gli archi i vincoli tra le variabili costituenti i nodi che l arco unisce. I 
vincoli unari sono rappresentati da archi che iniziano e terminano sullo 
stesso nodo X
i
, mentre i vincoli binari collegano 2 nodi X
i
 e X
j
. 
 
 
Fig. 1.3: Rappresentazione di vincoli unari e binari in un grafo di un CSP 
 
Esistono vari algoritmi che realizzano gradi diversi di consistenza. 
¾  Node-Consistency: consistenza di grado 1. Un nodo di un grafo Ł 
consistente se, per ogni valore nel dominio, i vincoli unari associati 
al nodo sono soddisfatti. Tutti i valori che non soddisfano i vincoli 
possono sicuramente essere eliminati dal dominio. Un grafo viene 
definito node-consistent se tutti i suoi nodi sono consistenti. Se, per 
esempio, in un CSP avessimo una variabile X con dominio iniziale 
[0..10], e il vincolo X>2, per rendere il grafo node-consistent Ł 
necessario eliminare i valori [0..2] dal dominio di X. 
¾  Arc-Consistency: consistenza di grado 2. La consistenza di grado 
2 si ottiene partendo da un grafo node-consistent verificando la 
consistenza di tutti gli archi. Un arco Ł consistente se per ogni valore 
nel dominio di una variabile esiste almeno un valore nel dominio 
dell altra variabile che soddisfi i vincoli associati all arco. 
PROBLEMI DI SODDISFACIMENTO DI VINCOLI 
 
9 
Ovviamente la rimozione di alcuni valori a causa dell arc-
consistency rende necessarie ulteriori verifiche che coinvolgano i 
vincoli unari sulle due variabili in gioco. Questo procedimento 
iterativo deve essere ripetuto fino a che la rete non converge ad uno 
stato stabile arc-consistent. 
¾  K-Consistency: consistenza di grado k. Dato un grafo consistente 
fino al grado k-1, la consistenza di grado k si ottiene scegliendo ogni 
possibile (k-1)-pla di variabili, consistente per definizione con i 
vincoli imposti, e cercando un valore per ogni ulteriore variabile del 
problema che soddisfi i vincoli fra tutte le k variabili prese in 
considerazione.  
Si dimostra che, se un grafo contenente n variabili Ł k-consistent 
con k<n, allora per trovare una soluzione Ł sufficiente una ricerca 
nello spazio restante. In un grafo di n variabili n-consistent, la 
soluzione pu  quindi essere trovata senza eseguire alcuna ricerca, 
basta avere l accortezza di scegliere nel giusto ordine le variabili da 
assegnare. Tuttavia, rendere un grafo n-consistent ha complessit  
esponenziale in n. Occorre quindi, anche in questo caso, ricercare il 
valore di k che fornisca il miglior trade-off tra la complessit  del 
processo iterativo di consistenza e la riduzione effettuata sullo spazio 
di ricerca.  
 
1.4 Funzioni Euristiche per l ordinamento delle 
variabili e la selezione dei valori 
  
Una Funzione Euristica, applicata ad un nodo n, valuta la distanza, 
quindi lo sforzo computazionale, che separa il nodo n dalla soluzione. 
Ordinando le strade aperte dalla piø  promettente alla meno 
 promettente , cioŁ da quella che ha una funzione euristica migliore a 
quella peggiore, Ł possibile raggiungere una buona soluzione in tempi 
ragionevoli anche per i problemi piø complessi.