Within soft constraint reasoning, weighted CSP (WCSP) provide a very convenient framework for modeling and solving many real-world optimization problems. Motivated for the relevance of WCSP model, this project aims at developing efficient solving algorithms for this model. We diferentiate between the centralized approach, where a WCSP instance is kept in a single computer, and the more recent distributed approach, where the instance is distributed among different computers (but none of them contains the whole instance). We also give special attention to the boolean case (namely, when variables only have two values to chose from) because it extends the famous boolean satisfiability problem (SAT) that is ubiquous in Computer Science. SAT solvers have improved their performance dramatically in the last 15 years, and some of the techniques responsible of this sucess can also be incorporated to boolean WCSP (being Max-SAT the most popular problem of this class). In the centralized case, we intend to achieve the overall goal by enhancing existing search algorithms with sophisticated techniques such as backjumping, learning and adaptive inference, and by improving current implementations with tailored linear programming solvers and more advanced data structures. In the distributed case, we intend to achieve the goal by combining existing search algorithms with local consistency enforcement and inference. In the distributed context, we also want to collect and/or build sets of benchmarks in order to compare the different alternatives. This project combines two research groups with complementary expertise.

Constraint reasoning techniques, developed in the context of AI research, have successfully solved many real problems. Although it is a mature field, there are many important active lines of research such as open CSPs, distributed CSPs, quantified CSPs and soft constraint problems. Another well-known AI topic is Planning. It has recently gained new strenth in the research community due to its reformulation in terms of graphs, search and constraint satisfaction. In this project we want to make progress in the open lines of research of both fields. We also want to exploit the close relation between constraint processing and planning. Our objectives are:

• Constraint reasoning. Our goal is to contribute to the efficient resolution of the new paradigms (open, distributed and quantified CSPs) as well as continue our work on soft constraints, where we have already made relevant contributions, extending the results to closely related models such as clausal formulas or bayesian networks. Since the problem is in general untractable, we also want to identify tractable classes (soluble in polynomial time).
• Planning. Our goal is to refine the methods based on heuristic search for planning. We also want to study and develop the combination of search and inference. We want to exploit the existence of symmetries to decrease the solving effort, which is a well-known topic in the constraint community.

We present this project as a continuation of REPLI (TIC2002-04470-C03) motivated by the good results and experience that was achieved. We have now a larger and more experienced team of researchers. The benefits of the project will be the accomplishment of the previous goals as well as the integration of different research groups with complementary expertise.

Constraint reasoning techniques, developed in the context of AI research, have successfully solved many real problems. Although it is a mature field, there are many important active lines of research such as open CSPs, distributed CSPs, quantified CSPs and soft constraint problems. Another well-known AI topic is Planning. It has recently gained new strenth in the research community due to its reformulation in terms of graphs, search and constraint satisfaction. In this project we want to make progress in the open lines of research of both fields. We also want to exploit the close relation between constraint processing and planning. Our objectives are:
Constraint reasoning. Our goal is to contribute to the efficient resolution of the new paradigms (open, distributed and quantified CSPs) as well as continue our work on soft constraints, where we have already made relevant contributions, extending the results to closely related models such as clausal formulas or bayesian networks. Since the problem is in general untractable, we also want to identify tractable classes (soluble in polynomial time).

Planning

Our goal is to refine the methods based on heuristic search for planning. We also want to study and develop the combination of search and inference. We want to exploit the existence of symmetries to decrease the solving effort, which is a well-known topic in the constraint community.

We present this project as a continuation of REPLI (TIC2002-04470-C03) motivated by the good results and experience that was achieved. We have now a larger and more experienced team of researchers. The benefits of the project will be the accomplishment of the previous goals as well as the integration of different research groups with complementary expertise.

The inclusion of soft constraints in the constraint-based reasoning model has connected this model with combinatorial optimization. This allows one to have a common view of both areas, exchanging methods between them. This project tries to use, integrate and extend ideas that have been shown successful for constraint reasoning in a double dimension:

• Soft constraints. Contribution to the issues caused by the inclusion of soft constraints in the constraint model, extending existing results for hard constraints. In particular, we will focus on soft constraint propagation and local consistency, resolution algorithms and their complexity, and the efficient formulation of real problems.
• Applications. To apply constraint techniques to two different fields: planning and uncertainty management. On planning, the idea of planning as heuristic search wll be extended to produce a temporal planner of high performance, combining a branch-and-bound scheme with prunning techniques based con constraint propagation. On uncertainty management, constraint-solving algorithms based on decomposition will be applied to bayesian networks and to the possibilistic model. Finally, other problems will be studied, in particular the optimization of circuit design. Project benefits include not only the above mentioned contributions and the resolution of the applications, but also the integration of research groups with complementary backgrounds.

Constraint technology offers advantages over traditional Operations Research methods to solve optimisation tasks. However, the CSP model presents some limitations because all constraints are mandatory. In real problems, constraints are often preferences, but if included in the CSP model an over-constrasined problem is produced. Then, the only option is to relax / remove some of the preference constraints by hand, but it is difficult to assure teh solution quality and this is not commercially satisfactory.

In the last years, several theoretical models as well as algorithms have been developed to represent and solve CSP with preferences. They have been produced in an academic context, but they are not fully available to industry. This project aims to bridge the gap between academic results and industrial needs. Specifically, the goal of ECSPLAIN is to develop methods, techniques and generic software, making it possible to address such problems in a systematic manner, thus insuring quality solutions to complex, constrained optimisation tasks. More specifically, the project focuses on the resolution of over-constrained problems and of problems involving multiple optimisation criteria and/or a wide variety of preference constraints.