Back to first pageBack to first page Centre for Artificial Intelligence of UNL
Browse our site
You are here:

Modern Techniques for Constraint Solving: The CaSPER experience

Main informationBy: Marco Correia (CENTRIA)

Date: Wednesday, 26th of January 2011, 14h00

Location: FCT/UNL, Seminar Room (Ed. II)
AbstractConstraint programming is a well known paradigm for addressing combinatorial problems which has enjoyed considerable success for solving many relevant industrial and academic problems. In the heart constraint programming lies the constraint solver, a computer program which attempts to find a solution to the problem, i.e. an assignment of all the variables in the problem such that all the constraints are satisfied.

This presentation describes a set of techniques to be used in the implementation of a constraint solver. These techniques aim at making a constraint solver more extensible and efficient, two properties which are hard to integrate in general, and in particular within a constraint solver. Specifically, we will address two major problems: generic incremental propagation and propagation of arbitrary decomposable constraints. For both problems we present a set of techniques which are novel, correct, and directly concerned with extensibility and efficiency.

All the presented material emerged from our work in designing and implementing a generic constraint solver. The CaSPER (Constraint Solving Platform for Engineering and Research) solver does not only act as a proof-of-concept for the presented techniques, but also serves as the common test platform for the many discussed theoretically models. If time allows, this presentation will also cover the first successful application of the resulting platform for addressing an open research problem, namely finding good heuristics for efficiently directing search towards a solution.
Short-bioMarco Correia is a PhD student at FCT/UNL and a member of CENTRIA. His work
focus on the design and implementation of the constraint solving paradigm. He
is the developer of CaSPER, an efficient constraint solver which has been used
for research and education within the constraint programming group at CENTRIA.
Centre for Artificial Intelligence of UNL
Departamento de Informática, FCT/UNL
Quinta da Torre 2829-516 CAPARICA - Portugal
Tel. (+351) 21 294 8536 FAX (+351) 21 294 8541

Fundacao_FCT