A constraint solver for model‐based engineering

Article type: Research Article

Authors: Mauss, Jakob | Seelisch, Frank | Tătar, Mugur

Affiliations: DaimlerChrysler AG, Research Information and Communication, Knowledge‐based Engineering, 10559 Berlin, Alt‐Moabit 96a, Germany E‐mail: {Jakob.Mauss, Frank.Seelisch, Mugur.Tatar}@DaimlerChrysler.com

Abstract: Model‐based applications in engineering, such as configuration, diagnosis or interactive decision‐support systems, require embedded constraint solvers with challenging capabilities. They do not only demand classical services as consistency checking and solving, but also the computation of minimal conflicts and explanations. Moreover, modelling engineered systems makes often use of expressive constraint languages, which mix continuous and discrete variable domains, linear and non‐linear equations, inequalities, and even procedural constraints. A positive feature of typical engineered systems is, however, that their corresponding constraint models have a bounded and even relatively small density (induced width). We present here a relational framework for constraint solving $\mathbb{RCS} $ that has been specifically designed to address these requirements. $\mathbb{RCS} $ is based on problem decomposition and variable elimination, exploiting the low‐density property. To analyse a set of constraints $\mathbb{RCS} $ builds a so‐called aggregation tree by joining the input constraints and eliminating certain variables after every single join. The aggregation tree is used by a set of conceptually simple algorithms to incrementally check consistency, compute solutions, minimal conflicts and explanations. We also report experimental results obtained with a prototype implementation of this framework.

Journal: AI Communications, vol. 17, no. 2, pp. 75-92, 2004