Mapping
In order to make use of a conceptual model we must have some way of executing it, that is mapping it to a design model. One advantage of separation of the conceptual modelling language from the design model is the ability to then rapidly experiment with different design models for the same conceptual model. While the strict separation of conceptual modelling language and design language is beneficial in terms of reuse of conceptual models and providing expressiveness to the conceptual modeller, it complicates the problem of how we map the conceptual model to an effective design model.
We wish to provide transparent and flexible ways of specifying how a conceptual model is mapped to a design model. This involves specifying not only how a specific constraint will be mapped to underlying constraints supported by the design language, but which constraints are mapped to which constraint solver. Because we have provided an expressive and extensible conceptual modelling language we need to provide ways to map these more complicated modelling structures to objects in the underlying constraint solvers. We can provide default mechanisms for mapping extensions of the conceptual modelling language to underlying solvers.
Experience in developing solutions to industrial constraint problems has shown that we will often need to use two or more solving technologies to tackle a hard constraint problem. Various constraints will be treated by one solver, while other constraints will be treated by another. Some constraints may be treated by two or more solvers. When we are using multiple solvers we not only need to specify which constraints are sent to each solver, and how they are mapped to that solver, but how the solvers will interact. Solvers may pass information about variables, eagerly or lazily; they may pass derived constraint information, eagerly or lazily. They may pass other information such as desired values, optimization criteria, or other solver specific information. The mapping language needs to encapsulate these possibilities at as high a level as possible. Clearly, we need the ability to refer to constraints and classes of constraints from the conceptual model in order to define such a mapping.
Syntactically the mapping will be specified by the programmer adding to the conceptual model. This could be done in two ways. One way is to treat the conceptual model as data. The mapping would operate on the conceptual model, producing a design model as output. The second way is to treat the conceptual model as a program. In this case the conceptual model would have not only a logical meaning, but also a default evaluation which, when executed, would produce correct answers. The mapping from the conceptual to the design model would, in this framework, modify the behaviour of the conceptual model without modifying its logical meaning.
Either way, the possible mappings to a design model are dictated by its semantics, which is the space of problem solving behaviours, or algorithms, it can express. In our view this space of behaviours can be summarised under five headings:
- decomposition into subproblems;
- posting constraints to solvers;
- communication between solvers;
- local/global search control;
- subproblem algorithm integration.
The mapping from conceptual to design model can be achieved by two kinds of transformation:
Logical transformations, which map conceptual models to conceptual models; examples are decomposition, reformulation, tightening and linking.
Behavioural transformations which map the conceptual model to a design model; examples are posting constraints to solvers, adding search behaviour, and integrating subproblem algorithms.
Other important issues arise in the construction of mapping languages. Some conceptual modelling constructs will not be supported by the underlying constraint solvers to be used. For example, expressions involving polynomials in constraints cannot be posted to a MIP solver. We need to effectively detect when no mapping is possible and communicate the reasons why to the author of the model.