MINION: A Fast, Scalable, Constraint Solver
Ian P. Gent, Christopher Jefferson, Ian Miguel · 2006
Abstract. We present Minion, a new constraint solver. Empirical results on standard benchmarks show orders of magnitude performance gains over state-of-the-art constraint toolkits. These gains increase with problem size – Minion delivers scalable constraint solving. Minion is a general-purpose constraint solver, with an expressive input language based on the common constraint modelling device of matrix models. Focussing on matrix models supports a highly-optimised implementation, exploiting the properties of modern processors. This contrasts with current constraint toolkits, which, in order to provide ever more modelling and solving options, have become progressively more complex at the cost of both performance and usability. Minion is a black box from the user point of view, deliberately providing few options. This, combined with its raw speed, makes Minion a substantial step towards Puget’s ‘Model and Run ’ constraint solving paradigm. 1