LIP6 2001/009
- Thesis
Intégration de Mécanismes de Réécriture dans un Système de Satisfaction de Contraintes - A. Liret
- 197 pages - 10/12/2000- document en - http://www.lip6.fr/lip6/reports/2001/lip6.2001.009.pdf - 1,434 Ko
- Contact : Anne.Liret (at) nullbte.bt.com
- Ancien Thème : OASIS
- Keywords : constraint satisfaction problem, hybrid solving, symbolic constraint rewriting, dynamic control object-oriented language, declarative language
- Publisher : Valerie.Mangin (at) nulllip6.fr
In the range of Constraint Satisfaction Problems (CSP), a great deal of techniques has been developed to deal with situations where problem solving is described by solution's characteristics, rather than a solving procedure. For several years, these techniques have been successfully applied to specify and solve a lot of difficult combinatorial problems, in numerous domains like planning, scheduling, time-tabling, dynamic network design. However, some combinatorial problems remain inappropriate or out of reach, essentially because of the general scope of the CSP formalism. This dilemma is not new: it's a classic effect of the NP-complete nature of CSP. However, there exist a lot of contexts where we can expect increasing the performances of a general constraint system, with the help of specialised knowledge, without decreasing the generality of applied techniques. Due to this duality of Constraint Satisfaction Problems' behaviour, on need to carefully choose a language which constraints are expressed in and also knowledge that we want this language to manipulate. In this thesis we study a particular manner of dynamically adding local knowledge with the aim to adapt CSP techniques to specific problem properties, using the Rewrite paradigm.
First, we identify concrete situations that clearly put in evidence the drawbacks of a CSP solver. We propose a solver dedicated to Rewriting Symbolic Constraints, called RCS. RCS produces redundant constraints, integrated to the constraint store, while solving the problem. Our implementation of our complete system (BackTalk+RCS) as well as our experiments upon finite-domain CSP problems lead us to propose on one hand, global criteria, which are particularly adapted to the category of cryptogram problems, and on the other hand, a language for defining declarative strategies to precisely control the execution of RCS. We use this language to observe the behaviour of RCS and dynamically measure the utility of RCS, regarding to the solution improvement. Finally we identify application domains which seem to be custom-built to such combination between constraints rewriting and constraint satisfaction-based solving.
First, we identify concrete situations that clearly put in evidence the drawbacks of a CSP solver. We propose a solver dedicated to Rewriting Symbolic Constraints, called RCS. RCS produces redundant constraints, integrated to the constraint store, while solving the problem. Our implementation of our complete system (BackTalk+RCS) as well as our experiments upon finite-domain CSP problems lead us to propose on one hand, global criteria, which are particularly adapted to the category of cryptogram problems, and on the other hand, a language for defining declarative strategies to precisely control the execution of RCS. We use this language to observe the behaviour of RCS and dynamically measure the utility of RCS, regarding to the solution improvement. Finally we identify application domains which seem to be custom-built to such combination between constraints rewriting and constraint satisfaction-based solving.