Exploiting non-standard CSP for leveraging application intelligence


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. The areas where ECSPLAIN will innovate are:

- Methodological support: to render development of applications a relatively straightforward and controlled process via means and methods for application developers for problem analysis, modelling and development.

- Algorithmic approaches: producing better algorithms to make things more efficient. These include combinations of existing techniques, and advances in hierarchical constraint satisfaction, iterative improvement methods, constraint propagation and interactive constraint satisfaction. Integration into commercial libraries is essential.

- Interaction techniques: to support interaction by developers, maintainers and end-users with the operational application in the form of explanations, decision support and interfacing.


SINTEF (Norway, coordinator)
SGTM TreeDAlgo
SGTM - TreeDAlgo (Morocco)
ILOG (France)
IIIA, CSIC (Spain)
NORSKOG (Norway)

Period: 01.01.00-30.06.02

CSP References

CSP Benchmarks