L'attività di ricerca di Dr. Kiziltan verte sulla programmazione
a vincoli (Constraint Programming, CP), la quale ha radici
nell'Intelligenza Artificiale (AI). La CP è una tecnologia
usata per risolvere molti problemi commerciali e industriali, quali
la configurazione, allocazione di risorse, trasporto e scheduling.
In CP, l'utente specifica i vincoli di un problema (ad esempio, il
consumo di potenza delle schede in una batteria di computer non può
eccedere una determinata potenza in ingresso), e un programma a
vincoli viene mandato in esecuzione per trovare una soluzione che
li soddisfa. A testimoniare l'importanza del ragionamento basato su
vincoli in AI è la mole di articoli pubblicati nelle ultime
maggiori conferenze e riviste di AI, quali l'Artificial
Intelligence Journal (AIJ), il Journal of Artificial Intelligence
Research (JAIR), l'International Joint Conference on Artificial
Intelligence (IJCAI), la European Conference on Artificial
Intelligence (ECAI), e la National Conference of the American
Association for Artificial Intelligence (AAAI).
Siccome la risoluzione di vincoli è in generale intrattabile, i
problemi possono diventare molto difficili al crescere della
dimensione. Occorrono perciò risolutori sempre più efficienti. Così
come risolvere vincoli può essere difficile, imporre vincoli può
rappresentare un problema notevole. L'efficienza di un programma a
vincoli dipende da molte scelte di modellazione. La formulazione di
un modello efficace per un determinato problema spesso richiede di
provare modelli alternativi e di ricorrere a "trucchi del
mestiere", quali modellazione ridondante e channeling. Può essere
un compito arduo anche per gli esperti. La crescente popolarità
dell'uso della CP ha fatto sorgere il bisogno di linguaggi di
modellazione di alto livello per consentire di mettere la
tecnologia alla portata di una più larga base di utenti. La ricerca
che si intende portare avanti è rivolta alla soluzione di questi
problemi, e ha lo scopo di trovare modi di aumentare l'efficienza e
l'usabilità degli strumenti di programmazione a vincoli. Argomenti
di particolare interesse sono: symmetry breaking, vincoli globali,
integrazione di tecniche di ricerca operativa in CP, e
modellazione.
Symmetry Breaking Le simmetrie si trovano
in molti problemi e ne aumentano le complessità combinatoria. Se la
simmetria non viene gestita, un risolutore di vincoli può sprecare
una grande quantità di tempo nella ricerca di soluzioni, prendendo
in cosiderazione assegnamenti simmetrici ma essenzialmente
equivalenti. Perciò, il "pruning" delle porzioni simmetriche dello
spazio di ricerca - ciò che prende spesso il nome di "symmetry
breaking" (o "rottura di simmetrie") - è spesso un punto cruciale
nella risoluzione efficiente dei problemi. Un'importante classe di
simmetrie è quella che origina dalle matrici di variabili di
decisione in cui righe e colonne sono simmetriche e possono essere
liberamente scambiate di posto senza per questo influire sulla
soddisfacibilità degli assegnamenti. Una matrice nxm con simmetrie
di righe e colonne ha n!m! simmetrie, che crescono in maniera
super-esponenziale. Allo scopo di rompere tali simmetrie in modo
semplice ed efficiente, ci occupiamo di studiare vincoli di
ordinamento. Dimostriamo l'efficacia di questi vincoli di
ordinamento per la rottura di simmetrie in un'ampia gamma di
problemi.
Vincoli Globali I vincoli globali ci
aiutano a specificare in modo semplice vincoli complessi e
ricorrenti. Encapsulano algoritmi di propagazione dedicati, che
sfruttano la struttura del vincolo e contribuiscono al pruning
dello spazio di ricerca in maniera efficace ed efficiente. Di
conseguenza, i vincoli globali sono tra i fattori chiave del
successo della CP. La nostra attività si colloca a metà tra il
progetto e l'implementazione di algoritmi di propagazione dedicati
per (nuovi) vincoli globali, utili in una varietà di applicazioni,
compresa la rottura di simmetrie. Inoltre, per fornire ai
programmatori a vincoli uno strumento di propagazione generale,
efficace ed efficiente, miriamo a sviluppare vincoli globali
"general purpose," che possano essere usati per propagare un'ampia
gamma di ulteriori vincoli globali. Infine, studiamo la complessità
computazionale della propagazione di vincoli globali, e mostriamo
che molti vincoli globali la cui propagazione completa è
intrattabile hanno parametri naturali, facili da calcolare, che li
rendono trattabili a parametri fissi.
Integrazione in CP di Tecniche di Ricerca
Operativa I problemi reali su larga scala
comprendono spesso vari sotto-problemi, con caratteristiche
diverse, che richiedono una particolare strategia di risoluzione.
Di conseguenza, c'è un interesse crescente nell'ibridazione tra
tecniche di risoluzione provenienti dalla CP e dalla Ricerca
Operativa (OR). Seguendo questa linea di ricerca, studiamo
l'integrazione in CP della ricerca locale e delle sue varianti,
come le meta-euristiche. Nello specifico, studiamo diverse forme di
integrazione del "local branching" - un buon metodo di ricerca
locale usato in Mixed-Integer Programming - con la ricerca ad
albero (backtrack tree search) estesa con la propagazione di
vincoli. Testiamo l'efficacia di questo nuovo framework su vari
problemi reali, tra cui i problemi di trasporto con vincoli di
caricamento.
Modellazione Per poter adottare una tecnologia
a vincoli nella risoluzione di un problema, il problema deve prima
essere modellato tramite variabili di decisione e vincoli su tali
variabili, che le soluzioni devono soddisfare. Molti problemi
combinatori si possono modellare in modo naturale usando variabili
insieme (set variable). Una variabile insieme assume come valore un
insieme di interi, quindi la dimensione del suo dominio è
esponenziale. La ricerca si è concentrata di recente su come
ottenere rappresentazioni efficaci, che consentano di ragionare sui
domini insieme in modo efficiente. Studiamo la complessità delle
possibili rappresentazioni, e cerchiamo rappresentazioni ibride che
possano facilitare la propagazione di una varietà di vincoli
insieme.
