Database of Case Studies Achieved Using CADP

Constraint Solving with LOTOS

Organisation: University of Regina (CANADA)

Method: LOTOS

Tools used: CADP (Construction and Analysis of Distributed Processes)

Domain: Constraint Programming.

Period: 2005

Size: 17 data types (500 lines of LOTOS)

Description: Solving a CSP (constraint satisfaction problem) consists in computing for a set of variables (defined on finite domains) an assignment that respects a set of constraints. This case study describes the use of LOTOS and CADP for CSP solving.

The basic idea is to represent the constraints in the data type part of LOTOS, so that the process part of LOTOS corresponds to the process of solving the CSP. In this way, the same LOTOS specification can be used to address different aspects of a CSP. First, the CSP is consistent if the LOTOS specification contains no deadlock. Second, simulation (respectively state space generation) corresponds to the generation of one solution (respectively all possible solutions).

To reduce the execution time of the state space generation, the C code generated by CAESAR.ADT for the data type part of the LOTOS specification is combined with an external library, providing implementations of dedicated constraint propagation algorithms, such as arc consistency. Using this combination, the execution time is significantly reduced: in the 29-queens example, state space generation time is reduced by a factor of almost three.

Conclusions: The combination of the C code generated for LOTOS data types with dedicated alogrithms for constraint propagation allows to significantly reduce the execution time of the state space computation.

The authors also note the quality of the code generated by CAESAR.ADT:
    "The experiments also show that some LOTOS data types operations are really fast."


Publications: [Mouhoub-Sadaoui-05] M. Mouhoub and S. Sadaoui. "Improving Lotos Simulation Using Constraint Propagation". In Proceedings of the 17th IEEE International Conference on Tools with Artificial Intelligence ICTAI'05 (Hong-Kong), December 2005.
Available on-line from our FTP site in PDF or PostScript
Contact:
Dr. Samira Sadaoui-Mouhoub
Assistant Professor
Department of Computer Science
University of Regina
3737 Wascana Parkway
Regina, SK S4S 0A2
Canada
Office: CW308.14
Tel: +1 306-337-2340
Fax: +1 306-585-4745
E-mail: sadaouis@cs.uregina.ca



Further remarks: This case study, amongst others, is described on the CADP Web site: http://cadp.inria.fr/case-studies


Last modified: Fri Feb 19 09:12:04 2016.


Back to the CADP case studies page