Minion: A fast scalable constraint solver

software
minion

Minion is a constraint solver, originally released in 2006, along with the paper ``Minion: A fast scalable constraint solver’’.

Minion is developed as open source on github. While Minion is still actively developed, with recent work including parallel search (in current releases) and making Minion usable as a library (this second part is still work in progress).

Minion’s input language is purposefully designed to be low-level and unlike many other solvers, Minion does not try to rewrite and pre-process inputs. This means Minion is best used as a backend for other languages which are both easier to write, and optimised. The two most useful are:

These high level languages also allow you to easily try targeting other solvers, including other CP solvers like Gecode, and also solvers for other frameworks, such as SAT.

Minion is designed as a ``black box’’ solver, providing relatively few options.

If you wish to cite Minion in an academic paper, the best reference is the ECAI 2006 paper: Gent, Jefferson, Miguel. Minion: A Fast Scalable Constraint Solver. ECAI 2006, pp. 98–102. PDF

Minion is Open Source software. It is currently released under the MPL 2.0 license, and available on github.

Minion was previously licensed under the GNU GPL v2, and hosted on sourceforge at http://sourceforge.net/projects/minion. There used to be a Minion mailing list, questions can now be asked at Github Discussions.

History

Minion was originally designed to see how fast a solver could be if designed to be with a simple core, particularly putting thought into how variables such as Booleans, and integers which can only take a few values, such as \(\{0,1,2,3\}\). The main constraint solvers I used when Minion came out, ILOG Solver and ECLIPSe (not to be confused with Eclipse, the Java text editor) did many things well, but it was unclear if they were leaving some performance opportunities for a smaller, faster solver. When Minion was released, empirical results on standard benchmarks showed orders of magnitude performance gains over state-of-the-art constraint toolkits.

Being open source was also practically useful, both ILOG Solver and Eclipse were closed source (Eclipse is now open source), and often performed rewrites to inputs that were undocumented, and not always benefical.

Unfortunately (or fortunately! for Minion’s existence), when creating Minion we were unaware of Gecode, which has similar goals, but some important differences in design (which I may write about one day, if anyone ever suggests to me they would care to hear about them!)

If you find Minion useful I would be interested to hear of your applications, you can drop me an email, or post on Github Discussions.

Benchmarks

Benchmarks are provided in the source distribution of Minion, together with programs to generate new benchmarks from various problem classes. As well as this, we aim to archive the specific benchmarks used in papers on Minion. As well as providing sample sets of benchmarks, this will enhance the reproducibility of our research. Researchers may run Minion on exactly the instances reported in our papers.

People

Many people have been involved in Minion over the years. Here is a (almost certainly incomplete) list. I won’t give links to their websites, because nowadays these have a depressing short life due to Universities deciding to shut the down, but most of them are easy to find on the search engine of your choice!

  • Andrea Rendl
  • Gökberk Kocak
  • James Wetter
  • Karen Petrie
  • Ian Gent
  • Ian Miguel
  • Lars Kotthoff
  • Neil Moore
  • Niklas Dewally
  • Nguyen Dang
  • Saad Attieh
  • Özgür Akgün
  • Peter Nightingale
  • Patrick Spracklen

Case studies

There have been many papers which use Minion. A few highlights:

Andrew Loewenstern used Minion and Tailor to schedule a nanoproteomic analysis system, modelling the movements of a robotic arm in Essence’ without prior constraint programming experience. Minion runs during the warmup phase to find a schedule for each job.

Andreas Distler and Tom Kelsey applied Minion to enumerate all monoids of orders eight, nine, and ten — problems previously unsolved — demonstrating Minion’s scalability on very large combinatorial problems. Published in Annals of Mathematics and Artificial Intelligence.

Victor Bovdi, Eric Jespers, and Alexander Konovalov used Minion to investigate units of finite orders in integral group rings. Their paper Torsion units in integral group rings of Janko simple groups is published in Mathematics of Computation. Victor Bovdi, Alexander Konovalov, and Steve Linton also used Minion and GAP together for torsion units in integral group rings of Conway simple groups, published in the International Journal of Algebra and Computation.

There are many more citations in Google Scholar.