# Model-Driven Constraint Programming

Rapha¨el Chenouard Laurent Granvilliers CNRS, LINA, Universit´e de Nantes, France.

raphael.chenouard@univ-nantes.fr Ricardo Soto CNRS, LINA, Universit´e de Nantes, France.

Pontificia Universidad Cat´olica de Valpara´ıso, Chile.

ricardo.soto@univ-nantes.fr CNRS, LINA, Universit´e de Nantes, France.

laurent.granvilliers@univ-nantes.fr

## Abstract

Constraint programming can definitely be seen as a model-driven paradigm. The users write programs for modeling problems. These programs are mapped to executable models to calculate the solutions. This paper focuses on efficient model management (definition and transformation). From this point of view, we propose to revisit the design of constraint-programming systems. A modeldriven architecture is introduced to map solving-independent constraint models to solving-dependent decision models. Several important questions are examined, such as the need for a visual highlevel modeling language, and the quality of metamodeling techniques to implement the transformations. A main result is the **sCOMMA** platform that efficiently implements the chain from modeling to solving constraint problems.

Categories and Subject Descriptors D.3.2 [*Programming Languages*]: Language Classifications—Constraint and logic languages; D.2.2 [*Software Engineering*]: Design Tools and Techniques—User interfaces; D.3.3 [*Programming Languages*]: Language Constructs and Features—Classes and objects, Constraints General Terms Languages Keywords Constraint Modeling Languages, Constraint Programming, Metamodeling, Model Transformation

## 1. Introduction

In constraint programming (CP), programmers define a model of a problem using *constraints* over *variables*. The variables may take values from domains, typically boolean, integer, or rational values.

The solutions to be found are tuples of values of the variables satisfying the constraints. The search process is performed by powerful solving techniques, for instance backtracking-like procedures and consistency algorithms to explore and reduce the space of potential solutions. In the past, CP has been shown to be efficient for solving hard combinatorial problems.

CP systems evolved from the early days of constraint logic programming (CLP). In a CLP system, the constraint language is embedded in a logic language, and the solving procedure combines the SLD-resolution with calls to constraint solvers [15]. The logic language can be replaced with any computer programming language Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

PPDP'08, July 16–18, 2008, Valencia, Spain.

Copyright c 2008 ACM 978-1-60558-117-0/08/07. . . $5.00
(e.g. C++ in ILOG Solver [26] or Java in Gecode/J [12]) and even term rewriting [11]. It turns out that the programming task may be hard, especially for non experts of CP or computer programming.

In this approach, modeling concerns are not enough to write programs, and it is often mandatory to deal with the encoding aspects of the host language or to tune the solving strategy. In response to this problem, almost pure modeling languages have been built, such as OPL [30] and Zinc [27].

The design of the last generation of CP systems has been governed by the idea of separating modeling and solving capabilities
(e.g. Essence [9] and MiniZinc [21]). The system architecture has three layers, including the modeling language, the solvers, and a middle tool composed by a set of solver-translators implementing the mappings. In particular, this approach gives important benefits: The full expressiveness of CP is supported by a unique highlevel modeling language, which is expected to be simple enough for non experts. The user is able to process one model with different solvers, a crucial feature for easy and fast problem experimentation.

The platform is open to plug new solvers.

Our work follows this solver-independent idea, but under a Model-Driven Development (MDD) approach [24], which is wellknown in the software engineering sphere. General requirements have been defined for MDD architectures in order to define concise models, to enable interoperability between tools, and to easily program mappings between models. The classical MDD infrastructure uses as base element the notion of a metamodel, which allows one to clearly define the concepts appearing in a model.

In this paper, the MDD approach is applied to a CP system.

The goal is to implement the chain from modeling to solving constraints. Our approach is to transform user solving-independent models defined through a visual modeling language to solver (executable) models using a metamodeling strategy. CP concepts like domains, variables, constraints, and relations between them are defined in a metamodel, and thus the transformation rules are able to map these concepts from a source language to a target one. It results in a flexible and extensible architecture, robust enough to support changes at the mapping tool level. Moreover, we believe that the study of metamodels for CP is of interest.

These ideas have been implemented in the **s-COMMA** platform [28]. The front tool allows users to graphically define constraint models. It is made on top of a general object-oriented constraint language [29]. Many solvers have been plugged in the platform such as ECLiPSe[31], Gecode/J [12], GNU Prolog [6] and Realpaver [14]. Upgrades are supported at the mapping tool, new solver-translators can be added by means of the AMMA platform [20].

The language for stating constraints in **s-COMMA** is clearly not the novel part of the platform, in fact it includes typical and stateof-the-art modeling constructs and features. Novelty arises from