Minion (solver)

Last updated

Minion is a solver for satisfaction problems. Unlike constraint programming toolkits, which expect users to write programs in a traditional programming language like C++, Java or Prolog, Minion takes a text file which specifies the problem, and solves using only this. This makes using Minion much simpler, at the cost of much less customization.

Contents

Minion has been shown to be faster than major commercial constraint solvers including CPLEX (formerly IBM ILOG). [1]

Overview

Minion was introduced in 2006 by researchers at the University of St Andrews as a “fast, scalable” solver for large and hard CSP instances. [2] The project provides a compact input language and a low-overhead C++ implementation aimed at throughput and memory efficiency. [3]

Design and features

Minion implements a range of variable and constraint types commonly used in CSP modelling, plus search heuristics and optimisation support. The solver architecture prioritises cache-friendly data structures and specialised propagators. Notably, the developers adapted watched literal techniques from SAT solving to speed up constraint propagation for, among others, Boolean sums, the element global constraint, and table constraints. [4] [5]

The modelling approach relies on a plain-text format (parsed by Minion) rather than embedding models into a host programming language. This reduces overhead and supports rapid “model-and-run” experimentation for large benchmark sets. [2]

Performance

In the original evaluation on standard benchmarks, the authors reported that Minion often ran between one and two orders of magnitude faster than state-of-the-art toolkits of the time (including ILOG Solver and Gecode) on large, hard instances, with smaller gains—or slowdowns—on easier problems. [2] Subsequent research has used Minion as a baseline solver in empirical studies and test generation tasks, reflecting its adoption within parts of the constraint programming community. [6]

Applications

Minion has been applied in academic work on combinatorial search, scheduling and test generation, and is available to other environments via wrappers (for example, from the R language). [7]

References

  1. ↑ Gent, Ian P.; Jefferson, Chris; Miguel, Ian. "Minion: A Fast, Scalable, Constraint Solver" (PDF).
  2. 1 2 3 Gent, Ian P.; Jefferson, Christopher; Miguel, Ian (2006). "Minion: A Fast, Scalable, Constraint Solver" (PDF). ECAI 2006. IOS Press. pp. 98–102. Retrieved 6 November 2025.
  3. ↑ "Minion Documentation (User guide)". Read the Docs. Retrieved 6 November 2025.
  4. ↑ Gent, Ian P.; Jefferson, Christopher; Miguel, Ian (2006). "Watched Literals for Constraint Propagation in Minion" (PDF). Proceedings of CP 2006. Retrieved 6 November 2025.
  5. ↑ "Minion Documentation — Constraints and modelling". Read the Docs. Retrieved 6 November 2025.
  6. ↑ "Minion: A Fast, Scalable, Constraint Solver (record)". University of St Andrews Research Portal. Retrieved 6 November 2025.
  7. ↑ "rminion: Use the Minion Constraint Solver from R". rdrr.io. Retrieved 6 November 2025.


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.