RICERCA ITALIANA     

Constraints and preferences as a unifying formalism for system analysis and solution of real-life problems

Università degli Studi di Padova

Abstract

Constraint programming is a multi-disciplinary research area where the fields of research range from Artificial Intelligence, to Operation Research, to Programming Languages, to Databases, and whose applications are present in many disciplines.

Constraint programming is a programming paradigm which is fundamentally different from the others, since it consists of modelling a problem in a declarative way (by stating its "constraints"), and then solving it via general procedures which explore the solution space and prune useless parts by an active use of the constraints. Typical successful applications of constraint programming are scheduling, rostering, vehicle routing, timetabling, and frequency assignment. Newly considered applications are protein folding, online configuration, web searching, and system and program analysis.

Research in the field of constraint programming started in the 70's within Artificial Intelligence, and since 1995 it has seen a significant increase of the theoretical and practical interest, with an annual international conference (CP), an international association (ACP), several workshops and volumes, an international journal, and five books. Europe leads the research in this field, but several groups working on constraint programming are scattered around the world. In Italy, research on constraint programming is done mainly by the groups participating to this project, where one of the main goals is to make these groups >>>

Principal Investigator

Francesca ROSSI Università degli Studi di PADOVA

Research Objectives

The goal of this project is to study the extension of existing frameworks and techniques for constraint programming, in particular with respect to innovative applications both to formal systems (e.g. security, program analysis) and to real problems (e.g. scheduling, bioinformatics). We will thus use constraints as a unifying approach and the applications as a motivation for the extensions of the languages and of the techniques for constraint solving.

Research units

To achieve this goal, we have gathered some of the main groups in Italy working in this area, in order to exploit the common knowledge for facilitating communication, and the complementary expertise for a fruitful cooperation leading to new theoretical and practical results. Such groups are present in the research field at international level and produce regularly practical and theoretical results which are well accepted by the international research community and which have started new lines of research in constraint programming.

More specifically:

-- unit 1 (Padova), which coordinates this project, has strong competences in soft constraints and preferences as well as in the application of constraint techniques to scheduling problems;

-- unit 2 (Udine) has experience in the definition and development of new logic programming languages with set-based constraints and also in the application of constraint techniques to bioinformatic >>>

Timescale

24 months

National and international background

Constraint programming [MS98,D03,Apt03] is a programming methodology which allows one to formalize the problem to solve in a purely declarative way, with the help of logical formulae called constraints. The computation phase is typically based on the search for one or more solutions which satisfy the set of all constraints. Constraint programming allows one to keep the formalization phase and the search for solutions completely separate. However, also the search for solutions is guided by the constraints to be satisfied, in order to significantly reduce the search space.

A constraint solver is an effective procedure that is able to check the satisfiability of constraints and to find solutions which satisfy all of them, if any. Several solvers have been proposed since the 80's, for several constraint domains and with different properties and
implementation techniques. Several of these solvers have been proposed within Constraint Logic Programming (CLP) [JM94], where currently the most widely used systms are SICStus Prolog [SICS] and ECLiPSe [ECLI]
which provide several constraint domains and corresponding solvers, and which have been used with success in the solution of optimization problems or in the search for feasible solutions for problmes with complex domains and with arbitrary objective functions.

The use of constraints over finite domains allows one to define combinatorial optimization problems, such as scheduling problems >>>