# Dominion A Constraint Solver Generator

Lars Kotthof f larsko@cs.st-andrews.ac.uk University of St Andrews Abstract This paper proposes a design for a system to generate constraint solvers that are specialised for specific problem models. It describes the design in detail and gives preliminary experimental results showing the feasibility and effectiveness of the approach.

## 1 Introduction

Currently, applying constraint technology to a large, complex problem requires significant manual tuning by an expert. Such experts are rare. The central aim of this project is to improve the scalability of constraint technology, while simultaneously removing its reliance on manual tuning by an expert. We propose a novel, elegant means to achieve this - a *constraint solver synthesiser*, which generates a constraint solver specialised to a given problem. Constraints research has mostly focused on the incremental improvement of general-purpose solvers so far. The closest point of comparison is currently the G12 project [1], which aims to combine existing general constraint solvers and solvers from related fields into a hybrid. There are previous efforts at generating specialised constraint solvers in the literature, e.g. [2]; we aim to use state-of-the-art constraint solver technology employing a broad range of different techniques. Synthesising a constraint solver has two key benefits. First, it will enable a fine-grained optimisation not possible for a general solver, allowing the solving of much larger, more difficult problems. Second, it will open up many new research possibilities. There are many techniques in the literature that, although effective in a limited number of cases, are not suitable for general use. Hence, they are omitted from current general solvers and remain relatively undeveloped. Among these are for example conflict recording [3], backjumping [4], singleton arc consistency [5], and neighbourhood inverse consistency [6]. The synthesiser will select such techniques as they are appropriate for an input problem. Additionally, it can also vary basic design decisions, which can have a significant impact on performance [7].

The system we are proposing in this paper, Dominion, implements a design that is capable of achieving said goals effectively and efficiently. The design decisions we have made are based on our experience with Minion [9] and other constraint programming systems.

The remainder of this paper is structured as follows. In the next section, we describe the design of Dominion and which challenges it addresses in particular.

We then present the current partial implementation of the proposed system and give experimental results obtained with it. We conclude by proposing directions for future work.