ECSPLAIN
Exploiting non-standard CSP for Leveraging Application INtelligence
The ECSPLAIN project is an international co-operation between partners in Norway, France, Morocco, and Spain. It is partly funded by the European Commission under the Fifth Framework Programme, contract number IST 1999-11969.
Introduction
Many industrial optimisation problems are naturally expressed in terms of constraints, for example those concerning scheduling, design, and configuration. Recognising this, several companies have put constraint technology to work, by commercialising constraint solvers. Their applicability has been proven as the number of industrial applications has rapidly increased. The principal paradigm used in constraint technology is the Constraint Satisfaction Problem model (CSP). While effective in many cases, this model has nevertheless a limitation that obstructs wider applicability, namely that all constraints are assigned the same importance and so must all be satisfied. In many problems, while some constraints are mandatory, others may only be representations of preferences. Including all preference constraints into a CSP can result in an over-constrained problem. In these cases, the only option is to relax / remove some of the preference constraints, thus "working around" the reality of the situation in order to assure a solution. Since quality is difficult to assure under such circumstances, this is not commercially satisfactory.
Constraint technology offers advantages over traditional Operations Research methods to solve optimisation tasks. The two main characteristics of constraint technology are its modelling power and the parameterisation possibilities in the resolution.
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 – 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.
Project Objectives
- To keep Europe the leader of constraint technology in the world. ECSPLAIN aims to develop methods, techniques and generic software for addressing over-constrained problems and complex industrial problems involving multiple optimization criteria and/or a wide variety of preference constraints. ECSPLAIN will enable explicit description of complex industrial problems, allowing expressive modelling of high level requirements, multiple optimization criteria and preferences.
- To improve the efficiency and quality in several areas of industrial activity. The developed methods and software will be applicable to a wide variety of optimization problems with preferences, including construction planning and forestry management, time tabling, resource allocation, routing and scheduling.
- To promote the project results and to strengthen IT business co-operation with Mediterranean and Middle East countries.
Partners
 |
SINTEF (Norway) is one of the
largest multi-disciplinary contract research
organizations in Europe. SINTEF
Applied Mathematics is the co-ordinating
partner of the ECSPLAIN project. SINTEF
contributions include
development of methodologies, solution
algorithms, and generic software. |
 |
NORSKOG
is a member organisation for forest owners.
NORSKOG is not a large organisation in number of
members, but the 220 forest owners (members)
represent more than 600,000 hectare (ha) of
productive forest and 1.2 million ha of
forestland. NORSKOG members harvest approximately
1 million m³ of timber annually. |
 |
SGMT |
 |
TreeDAlgo is a subsidiary company of the SGTM. The local web pages at TreeDAlgo for the ECSPLAIN project is available here. |
 |
Headquartered in France and the United
States, ILOG is
the world's leading provider of software
components. Founded in 1987, ILOG offers
embeddable optimization, visualization and
business rule components that shorten the
development time of enterprise applications for
the supply chain, telecommunications,
transportation, financial services and other
industries. ILOG has a leading market share of
the optimization market and is playing a defining
role in the emergence of the e-business software
components market. |
|
The CSIC (Spanish Council for Scientific Research) is the largest public research organization in Spain. With more that 2.000 permanent scientists distributed in 111 institutes, it performs scientific and technical research in all branches of knowledge. |
 |
The IIIA
(Artificial Intelligence Research Institute) is a
center of CSIC devoted to Artificial Intelligence.
It groups 13 permanent scientist, plus visitors,
engineers, post PhD fellows and PhD candidates,
performing active research on: Learning Systems,
Intelligent Agents, Logic Reasoning and Search,
Electronic Marketplaces, Autonomous Robots and
Music with AI The local web pages at CSIC/IIIA for the ECSPLAIN project is available here. |
Results
This section lists the publically available results of the ECPSLAIN project.
Publications
J-C.Régin, T.Petit, C.Bessière, J-F.Puget, "An Original Constraint Based Approach for Solving Over Constrained Problems", proceedings of 6th International Conference on Principles and Practice of Constraint Programming (CP2000), Singapore, September 2000, p.543-548. http://www.comp.nus.edu.sg/~cp2000/index.html This paper was also presented in ISMP2000 conference on Mathematical Programming (abstract available on proceedings, http://www.isye.gatech.edu/ismp2000/
T.Petit, J-C. Régin, C. Bessière, "Meta-Constraints on Violations for Over Constrained Problems", proceedings of Twelfth IEEE International Conference on Tools with Artificial Intelligence, Vancouver, British Columbia, Canada, November 13-15, 2000. http://www.ece.ubc.ca/ictai/
Pedro Meseguer "Lower bounds for non-binary Max-CSP" Workshop on Modelling and Solving Problems with Constraints (August 22), 14th European Conference on Artificial Intelligence (ECAI-2000). Pedro Meseguer and Marti Sanchez "Tree-based Russian Doll Search: Preliminary Results", Workshop on Soft Constraints, 5th International Conference on Principles and Practice of Constraint Programming (CP-2000). This paper is available at the address: http://www.math.unipd.it/~frossi/cp2000-soft/meseg.ps
P. Meseguer and M. Sánchez, "Tree-based Russian Doll Search: Preliminary Results", Soft Constraints, CP-2000 workshop, Singapore, September 2000.
T.Petit, J-C. Régin, C. Bessière, "Meta-constraints on violations for over constrained problems", 12th International Conference on Tools with AI, Vancouver, Canada, November 2000.
T. Petit, "Problemes sur-contraints", Proceedings of JDOC'2001, p.96-99, Journees des doctorants de l'ecole I2S, Montpellier, France, March 6-8, 2001.
T. Petit, "Problemes sur-contraints", Journees Franciliennes de Recherche Operationnelle, Paris, June, 2001
M. Bouzoubaa, T. Bouzoubaa, "Projet européen Ecsplain : Problèmes de construction de tunnels et de gestion de forêts", 7th French Journées nationales sur la résolution pratique de problèmes NP-Complets, Toulouse, France, 27-29 June 2001
T. Petit, J-C. Regin and C. Bessiere, "Algorithmes de filtrage specifiques pour les problemes sur-contraints" Proceedings of the JNPC'2001 conference, Toulouse, France, june 27-29, 2001.
T. Petit, "Generalization of constructive disjunction for over-constrained problems" (invited talk) Conference INFORMS-2001, Miami, Florida, USA, November 4-7, 2001
T. Petit, J-C. Regin and C. Bessiere, "Specific Filtering Algorithms for Over-Constrained Problems", Accepted for publication in the proceedings of CP'2001, Paphos, Cyprus, Nov 26 - Dec 1, 2001.
J-C. Regin, T. Petit, C. Bessiere and J.F. Puget, ``New Lower Bounds of Constraint Violations for Over-Constrained Problems'', Accepted for publication in the proceedings of CP'2001, Paphos, Cyprus, Nov 26 - Dec 1, 2001.
P. Meseguer, J. Larrosa, M. Sanchez, "Lower Bounds for Non-binary Constraint Optimization Problems", 7th International Conference on Principles and Practice of Constraint Programming, CP-01, Cyprus, Nov-2001.
P. Meseguer, M. Sanchez, "Specializing Russian Doll Search", 7th International Conference on Principles and Practice of Constraint Programming, CP-01, Cyprus, Nov-2001.
P. Meseguer, N. Bouhmala, T. Bouzoubaa, M. Irgens, M. Sanchez, "Current Approaches for Solving Over-Constrained Problems", accepted for publication on Constraints journal, final version sent in December 2001.
J.Larrosa, P.Meseguer and M.Sanchez, "Pseudo-tree search for Soft Constraints", 15th European Conference on Artificial Intelligence, Lyon, France, July 21-26, 2002, 131-135.
P.Meseguer, M.Sanchez and G.Verfaillie, "Opportunistic Specialization in Russian Doll Search", 8th International Conference on Constraint Programming CP-2002, Cornell, USA, September 8-13, 2002, (in press).
T.Petit, J.Ch.Regin and Ch. Bessiere, "Range-Based algorithm for Max-CSP", Workshop on Modelling and Solving CSP, ECAI2002 Lyon, France, July 21-26, 2002. 8th International Conference on Constraint Programming CP-2002, Cornell, USA, September 8-13, 2002, (in press).
Benchmarks
A comprehensive overview of collected and produced benchmarks is given on the benchmark page.
Project reports
<<-------- Under construction ---------->>
Contacts
Project Manager: Mouhssine Bouzoubaa,
SINTEF Applied Mathematics
tel: +47 22 06 73 00, fax: +47
22 06 73 50 email: Mouhssine.Bouzoubaa@math.sintef.no
Research Director Geir Hasle, SINTEF Applied
Mathematics
tel: +47 22 06 73 00, fax: +47
22 06 73 50 email: Geir.Hasle@math.sintef.no