You are here


Weigted Soft Constraints: Centralized and Distributed Cases
Jan 2010 - Dec 2012
Project description
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.
Research Line
Constraint Satisfaction