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

Dynamic Variable Elimination During Propagation Solving

Main informationBy: Christian Schulte (KTH - Royal Institute of Technology, Sweden)

Date: Friday, 10th of December 2010, 11h30

Location: FCT/UNL, Seminar Room (Ed. II)
AbstractConstraint propagation solvers interleave propagation (removing impossible values from variables domains) with search. Propagation is performed by executing propagators (removing values) implementing constraints (defining impossible values).

In order to specify constraint problems with a propagation solver often many new intermediate variables need to be introduced. Each variable plays a role in calculating the value of some expression. But as search proceeds not all of these expressions will be of interest any longer, but the propagators implementing them will remain active.

In this talk I show how we can analyse the propagation graph of the solver in linear time to determine intermediate variables that can be removed without effecting the result. Experiments show that applying this analysis can reduce the space and time requirements for constraint propagation on example problems.

Joint work with Peter Stuckey, NICTA & U Melbourne, Australia.
Short-bioChristian Schulte works as associate professor at the unit Software and Computer Systems, School of Information and Communication Technology, KTH - Royal Institute of Technology in Stockholm, Sweden. He is director of undergraduate studies (master/advanced level) for the strategic area Communication: Services and Infrastructure. He also works part-time as expert researcher at the Computer Systems Laboratory of the Swedish Institute of Computer Science (SICS).
His research interests include programming languages, in particular concurrent and constraint-based programming languages, constraint programming, and distributed systems. His current research focus is on models, architectures, and implementation techniques for constraint programming systems. He is heading the development of Gecode as an attempt to construct an open, free, portable, accessible, and efficient environment for developing constraint-based systems and applications.
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