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 in our ECAI 06: details are on the references page.

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, many papers which use Minion. A few are presented here, this selection is made fairly randomly, and also covering mostly older uses (just due to not keeping the page up to date)

Andrew Loewenstern is using Minion and Tailor to schedule the CB1000 Nanoproteomic Analysis System. Without prior experience in constraint programming, he was able to model the problem of scheduling the movements of the robotic arm and access to the separation chamber in Essence' and solve it; improving the solution a previous approach provided significantly. Each time the machine performs a job, Minion runs and finds a schedule during the warmup phase.

Andrew presented a paper describing his work at the The 15th International Conference on Principles and Practice of Constraint Programming.

Andreas Distler and Tom Kelsey applied Minion to the problem of finding the number of monoids of orders eight, nine, and ten. They demonstrated the scalability of Minion on very large problems which were previously unsolved. This application also shows the effectivity of the black-box approach to using Minion; i.e. solving a problem without having to tweak lots of parameters.

Their work has been published in Annals of Mathematics and Artificial Intelligence.

Amba Kulkarni, Sheetal Pokar and Devanand Shukl of the University of Hyderabad are using Minion to develop a constraint based parser for Sanskrit. Their efforts are described in this publication.

Adam Benzan is using Minion to generate random crossword puzzles on the fly.

Victor Bovdi, Eric Jespers and Alexander Konovalov investigated units of finite orders in integral group rings, and used Minion to find possible partial augmentations (that is, sums of coefficients of group ring elements over conjugacy classes of group elements) for such units. Their paper, Torsion units in integral group rings of Janko simple groups, is published in the Mathematics of Computation journal.

Victor Bovdi, Alexander Konovalov and Steve Linton also used Minion and GAP together to find Torsion units in integral group rings of Conway simple groups. This work is published in the International Journal of Algebra and Computation.

The Institute for Software Technology at the Graz University of Technology is using Minion for debugging and testing programmes.

Jean-Michel Rey at the Etang Vallier Resort uses Minion to run an automated booking system for chalets and other accommodation.

Minion was used in the paper Model-based simulation and configuration of mobile phone networks - The SIMOA approach presented at WAITS 2012 workshop, at ECAI 2012.

There are many more people who use Minion in their work and cite it in their papers. A list of citations can be obtained from Google Scholar.

Syntax Highlighting for Minion Input Format

Here are some syntax highlighting tools for Minion input (input format Minion 3 and newer) with installation instructions. These have not been kept up to date, but are provided for any interested users.