Computer Science @ University of St Andrews

University of St Andrews crest

The Minion Constraint Solver

The Minion Constraint Solver

MINION, is a new constraint solver, which is very fast and scales well as problem size increases. 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.

  • Watched Literals and Learning for Constraint Programming (EPSRC 2007-11, £382,018).

    This research addresses a major challenge, that of how advances made in the closely-related field of propositional satisfiability (SAT) can be made in constraint solving. Specifically, we will research watched literals as a method for developing efficient constraint propagators (algorithms for performing inference with constraints). In the context of the Minion constraint solver, we will perform algorithm engineering to improve understanding of fundamental implementation issues, and how we can efficiently enable constraint solvers to learn from their mistakes.