|
Département d'ingénierie informatique |
Researcher : R. Collet, G. Dooms, S. Gualandi, L. Quesada, N. Tran Sy, S. Zampelli
Collaborations :
- Bioinformatic Research Center, Glasgow University, UK
Description :
Constraint programming (CP) is software technology for declarative and effective solving of large, particularly combinatorial, problems in areas such as planning, scheduling, sequencing, resource allocation, design and configuration. Solving such problems is, in general, NP-hard. Designing efficient algorithms for a specific problem can be though. Constraint programming, or more generally Constraint Satisfaction Problems (CSP), allows to solve these problems. The objective of constraint programming is to provide methods, techniques and tools to solve CSP. The hope is to reduce the development time while preserving the efficiency of specialised algorithms. Constraint programming has been identified by the ACM (Association for Computing Machinery) as one of the strategic directions in computer research.
Our main focus in CP is the development of methods and tools for specific classes of problems.
- We developped a new approach for automated test data generation of imperative programs containing integer, boolean and/or float variables, as well as arrays and procedures. Given a path of the program, a path constraint is derived and solved to obtain a test case. The constraint solving is carried out based on a consistency notion, combining finite and continuous computation domains. The COTTAGE system, a 13,000 Java lines software, implements our approach for C programs.
- We were also interested in the extension of constraint programming techniques for solving differential equations.
- An extension of computation domain is also been investigated for the analysis of biochemical network. This invloves the design of graph domain variables, constraints on graphs, and suitable propagator for the analysis of biochemical networks.
- Constraint programming is also investigated for finding patterns in large biochemical networks. This is closely related to solving the subgraph isomorphim using constraint programming techniques.
- A subcontracting confidential work for the European aerospace industry is performed which aims to apply constraint programming techniques to advanced aerospace applications.