Foto del docente

Zeynep Kiziltan

Ricercatrice confermata

Dipartimento di Informatica - Scienza e Ingegneria

Settore scientifico disciplinare: INF/01 INFORMATICA

Temi di ricerca

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.

Ultimi avvisi

Al momento non sono presenti avvisi.