Foto del docente

Zeynep Kiziltan

Assistant professor

Department of Computer Science and Engineering

Academic discipline: INF/01 Informatics

Research

The research of Dr. Kiziltan focuses on Constraint Programming (CP) which has its roots from Artificial Intelligence (AI). CP is a highly successful technology for solving a wide range of problems in business and industry like  configuration, resource allocation, transportation, and scheduling. The user specifies the constraints to a problem (for example, the power demand of the cards in a computer rack cannot exceed the capacity of the fitted power supply), and a constraint program is run to find a solution which satisfies these constraints. The importance of constraint reasoning in AI is witnessed by the volume of related papers published in the recent top AI conferences and journals, such as the Artificial Intelligence Journal (AIJ), the Journal of Artificial Intelligence Research (JAIR), the International Joint Conference on Artificial Intelligence (IJCAI), the European Conference on Artificial Intelligence (ECAI), and the National Conference on Artificial Intelligence (AAAI).

 

As constraint solving is intractable in general, problems might be very difficult to solve as their size increase. Therefore, there is always a need for more efficient solvers to cope with ever difficult problems. Just like solving constraints can be hard, stating constraints can be challenging. The efficiency of a constraint program depends on many modelling decisions. Formulating an effective model for a given problem often requires trying alternate models and using ``modelling tricks'' such as redundant modelling and channelling. This could be a challenge even for modelling experts. The increasing use of CP necessitates higher level modelling languages to facilitate  the exploitation of the available technology and to make CP reachable to a wider user base. My research goals are aimed at addressing these problems, looking for ways to enrich the efficiency and the usability of the CP tools. I am in particular interested in the following topics: symmetry breaking, global constraints, integration of Operations Research techniques into CP, and modelling.



Symmetry Breaking Symmetries occur in many problems and increase their combinatorial complexity. If symmetry is not dealt with, a constraint solver may waste a large amount of time by considering symmetric but essentially equivalent assignments during search for solutions. Hence, pruning the symmetric parts of a search space, which is often referred to as symmetry breaking, is often crucial to the success of solving problems efficiently. An important class of symmetries arise in matrices of decision variables where rows and columns are symmetric and can be freely swapped without affecting the satisfiability of assignments. An nxm matrix with row and column symmetry has n!m! symmetries which grow super exponentially. In order to break such symmetries in a simple and efficient way, we investigate ordering constraints. We demonstrate the effectiveness of these symmetry breaking ordering constraints on a wide range of problems.


 

Global Constraints Global constraints help us specify complex and recurring constraints in a simple way. They encapsulate dedicated constraint propagation algorithms which exploit the structure of the constraint and help prune the search space effectively and efficiently. Consequently, global constraints are one of the factors central to the success of CP. Our work lies within the design and implementation of dedicated propagation algorithms for (new) global constraints which are beneficial in a variety of applications, including symmetry breaking. Moreover, in order to provide a general, effective and efficient means of propagation to constraint programmers, we aim at developing ''general purpose'' global constraints which can be used to propagate a wide range of other global constraints. Furthermore, we study the computational complexity of propagating global constraints and  show that many global constraints which are intractable to propagate completely have natural parameters which make them fixed-parameter tractable and which are easy to compute.

 

Integration of Operations Research Techniques into CP Large-scale real-world problems often include several sub-problems, each with different characteristics, requiring a particular solving strategy. As a consequence, there is an emerging interest to focus on hybridisation of the solving techniques that come from CP and Operations Research (OR). Following this line of research, we study the integration of local search and its variants such as meta-heuristics into CP. In particular, we investigate different forms of integration of local branching, which is a successful local search method used in Mixed-Integer Programming, into backtrack tree search augmented with constraint propagation. We test the effectiveness of this new framework on several different real-world problems including vehicle routing problems with loading constraints.

 

Modelling To employ a CP technology to solve a problem, the problem must first be modelled using decision variables and constraints on these variables that solutions must satisfy. Many combinatorial problems are naturally modelled using set variables. A set variable takes as value a set of integers and thus its domain size is exponential. Recent research has focused on devising effective representations to reason with set domains efficiently. We study the complexity of possible representations and investigate interesting hybrid representations which can facilitate the propagation of a variety of set constraints.

Latest news

At the moment no news are available.