MINION

Fast, Scalable Constraint Solving

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.

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 lean, highly-optimised implementation. 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.

If you wish to cite MINION in an academic paper, the best reference at the minute is our recently accepted paper at ECAI 06: details are on the references page. We have no preference on the typography of the word MINION.

Minion is Open Source software, licensed under GNU General Public License Version 2. Minion is maintained as a SourceForge project. There is a MINION mailing list, details of which can be found at: https://mailman.cs.st-andrews.ac.uk/mailman/listinfo/mug

If you find MINION useful we would be very interested to hear of your applications. Please drop us an email on the mailing list or post something on our guestbook.

News

  • October 27, 201e. Minion 1.6.1, a minor bugfix release, has been released.

    Changelog:

  • Improvements:
    • Fixed a slowdown in reification of equality constraints
    • The windows binary now runs on all versions of Windows back to 32-bit Windows XP.

  • September 30, 2013. Minion 1.6 has been released. We have had no "wrong answer" bugs in over a year, and Minion has been stable for a number of years. Therefore we decided to leap-frog 1.0 and go directly to 1.6 (instead of 0.16).

    Changelog:

    • Bugfixes:
      • Fix an occasional crash when minion exits (this only happened after all output was produced.)
    • Improvements:
      • Added an implementation of the shortstr2 propagator (as published in IJCAI 2013), and SHORTTUPLES, which is a compressed form of tuples used by ShortSTR2 and some other propagators.
      • Added the command line option '-map-long-short' to automatically compress standard tuples into short tuples, for use with shortstr2 and haggisgac (also published in IJCAI 2013)
      • Added an implementation of the mddc, negativemddc and str2plus propagators.
      • All constraints now work with negative values, in particular pow, div and mod.
      • Minion can now support 64-bit domains on both 32-bit and 64-bit processors. Enable with the DOMAINS64 compile time option to CMake.
    • Other changes:
      • Many old pieces of code were cleaned up or deleted.

  • December 17, 2012. Minion 0.15 has been released. Merry Christmas!

    Changelog:

  • Improvements:
    • The Mac version of Minion is now much faster (up to 30%), due to a change of compiler switches.
    • The 'HaggisGAC' constraint has been added. This constraint is allows users to specify their own constraints, using "don't care" values.
    • The '-outputCompressed' flag has been added, which makes Minion try to compress an input file by removing implied constraints. In some situations this can lead to big speed increases, in others a small slowdown. We are particularly interested in any feedback on this option.

  • July 27, 2012. Minion 0.14 has been released.

    Changelog:

    • Bugfixes:
      • When Minion was asked to find all solutions to a problem that could be solved without search, it returned the one solution then segfaulted. This was corrected, it does not change the set of solutions but does now exit correctly.
    • Improvements:
      • Minion is now able to split the remaining search to allow parallel search. See the manual for further details. This introduces the -split command-line switch.
    • Other changes:
      • The -resume-file commandline switch has been removed because its function is no longer necessary as resume files are now self-contained. See the manual.

  • May 1, 2012. Minion 0.13 has been released.

    Changelog:

    • Bugfixes:
      • Two 'incorrect answer' bugs were fixed, involving Booleans. These are both cases of invalid input being accidentally accepted.
      • According to the manual reify(C,b) would only accept a BOOLEAN variable, but the code would accept other variables, and then produce a wrong answer. The code now works correctly.
      • The '!' operator would accept non-boolean variables, and then produce incorrect results. The input is now rejected.
      • SAC did not propagate as much as it should. This never produced incorrect answers, only a slightly larger search in some cases.
      • Minion could produce incorrect answers when too large inputs were given (around 2^31). Now sensible error message are produced.
      • Previously when using a 'MINIMISING' condition, Minion would print out the negative of the optimal value found.
    • Improvements:
      • Previously variables left out of the variable ordering were not branched on. While this was expected behaviour, it could lead to Minion printing out invalid values if these variables were not assigned by propagation. Now Minion always branches on all variables.
      • Add flag '-printonlyoptimal' which prints only the optimal solution for optimisation problems, not the intermediate solutions.
      • All constraints can now be reified.
      • Big speed improvements to some cases of element
      • -varorder=random now uses a dynamic random order, rather than a static one.
      • Make memory allocation lazy. This is more efficent when we don't need much of it.
      • Produce better error messages for invalid input.

  • March 21, 2011. Minion 0.12 has been released.

    Changelog:

    • Bugfixes:
      • fix visualiser to work with more recent versions of Haskell
      • fix memory reporting on Mac OS X
      • fix some numerical issues with CPU time reporting
      • fixes to watched-or and watched-and constraints
    • Misc improvements:
      • more robust and more thorough testing
      • better error messages when variables are used with incompatible constraints

  • February 12, 2011. Minion 0.11 has been released.

    Changelog:

    • New features:
      • added negation of diseq constraint
      • added negation of watched-and constraint
      • enable watched-or to work with bound variables
    • Bugfixes:
      • bug fixes with nested watched-and and watched-or
      • bug fixes in the tester
    • Misc improvements:
      • improvements in documentation
      • integrate new implementations of gcc and gccweak with many more compile-time options
      • added visualisation scripts
      • added literal tightness statistics to -instancestats
      • Minion might work on OpenSolaris now
    Never Trust a Monster to do the Work of an Evil Scientist.

  • March 17, 2010. Minion 0.10 has been released.

    Changelog:

    • Nauty is now included by default for automatic symmetry detection.
    • New features:
      • added watchvecexists_less constraint
      • added quick lexless constraint
      • added lightweight table constraint
      • new flag -instancestats that will give various properties about the instance
      • new flag -searchlimit to limit only time spent in search and not in preprocessing
    • Bugfixes:
      • time limits are now taken into account during preprocessing as well
      • some of the generators were getting old and have been updated
      • reification of unary constraints works properly now
      • set constraints on empty sets now work
      • several bugfixes for watched constraints
    • Misc improvements:
      • speed improvements and memory for the parser
      • reduced memory requirements
      • improved testing
      • tidier reimplementation of the search manager
      • bumped minimum Mac OSX version from 10.4 to 10.5

  • March 12, 2010.

    We are applying again to be a Google Summer of Code mentoring organisation. Please take a look at our ideas page.

  • September 28, 2009.

    We have added first case studies to the new applications page.

  • August 21, 2009. Minion 0.9 has been released.

    Changelog:

    • New features:
      • added ability to abort and resume runs
      • added lex[rv] (which achieves GAC with repeated variables) and lex[quick] constraints
      • added -cpulimit flag to limit CPU rather than wall time
    • Misc improvements:
      • various source code cleanups
      • converted the benchmarks to Minion 3 format
      • speedup for input file parsing
      • added support for Windows without Cygwin
      • reduced memory usage

  • August 19, 2009. We are officially retiring the Subversion repository. The source code can be found in our new Git repository from now on.
  • April 06, 2009. Minion 0.8.1 has been released.

    There are some changes and bugfixes, for details please see the news item.

  • March 19, 2009. Our Google Summer of Code application has been rejected.
  • March 11, 2009. We have applied to be a Google Summer of Code mentoring organisation. Please take a look at our ideas page.
  • February 18, 2009. Minion 0.8 has been released.

    There are numerous changes and bugfixes, for details please see the changelog.

  • June 30, 2008. Release Candidate 1 of MINION 0.7.0 is available. There are numerous significant changes and also a greatly expanded manual including tutorial material. It can be downloaded from our download page.
  • May 17, 2008. MINION 0.6.0 has been released. The major changes are
    • Bugs fixed:
    • -check was always enabled. This slowed down problems which found many solutions (hundreds per second)
    • New features:
    • hamming, watchedvecexists_less, watchedvecexists_and, negativetable.
    • Faster performance at root node.
    • New algorithm for solving problems whose solutions for a group.
    • Accept gzipped and bzip2ed input.
    • Better error messages from invalid command line options or input files.
    • -check now faster when activated.
    • Documentation improvements.
    • Many internal improvements and cleanups.
  • February 8, 2008. MINION 0.5.1 has been released. The major changes are
    • The windows version of Minion now requires 'cygwin'.
    • The 'gacelement' constraint has been renamed 'gacelement-deprecated'.
    • Several bugfixes and minor improvements.
    • You can read more at the detailed changelog.
  • January 17, 2008. MINION 0.5.0 has been released. The major changes are
    • considerable stability improvements
    • several bugfixes
    • new, enhanced input format
  • May 9, 2007 The current svn-version of MINION contains a translator that creates MINION instances from Essence' problem models. More information about this translator (including examples) can be found here.

[ Home | Download | Benchmarks | Bugs | Manual | Case studies | References | People | Guestbook ]


Minion is hosted by sourceforge.net
SourceForge.net Logo