References
Minion was started as an academic research project, and we envision that it will continue to be used in a research context, as well as being of use to the wider CP community.
Logical constraints and reification
Minion supports reification of any constraint: for a constraint C and boolean variable b, reify(C, b) means ‘C is satisfied iff b’. Reification is very useful for writing logical combinations of constraints. Also Minion has an ‘or’ meta-constraint (named watched-or) that allows the user to write ‘C1 or C2 or C3…’ for a set of arbitrary constraints C1, C2, C3… The algorithms used to implement these features are described in the following paper.
Christopher Jefferson, Neil Moore, Peter Nightingale, and Karen E. Petrie,
Implementing Logical Connectives in Constraint Programming,
Artificial Intelligence, Volume 174, pages 1407-1429, 2010.
Cardinality constraints
Minion has a strong (GAC) implementation of the all-different constraint (named gacalldiff) and for the extended Global Cardinality constraint (named gcc and gccweak) that provide strong (GAC) propagation on the target variables, and two different levels of propagation on the cardinality variables. These constraints are described in the following papers.
Peter Nightingale,
The Extended Global Cardinality Constraint: An Empirical Survey,
Artificial Intelligence, Volume 175 issue 2, pages 586-614, doi:10.1016/j.artint.2010.10.005, 2011.
Ian P. Gent, Ian Miguel and Peter Nightingale,
Generalised Arc Consistency for the AllDifferent Constraint: An Empirical Survey,
Artificial Intelligence, Volume 172 number 18, pages 1973-2000, 2008.
Table constraints
The following paper discusses data structures for some of the table constraint propagators in Minion.
Ian P. Gent, Christopher Jefferson, Ian Miguel and Peter Nightingale,
Data Structures for Generalised Arc Consistency for Extensional Constraints, (slides)
in Proceedings of the Twenty Second Conference on Artificial Intelligence (AAAI-07), pages 191-197, 2007.
Minion has a set of table constraints that take tables of ‘short tuples’ (which are tuples that assign a subset of the variables and leave others free). In some cases a table of short tuples can be much smaller (and faster to process) than a conventional table. The following papers describe the algorithms implemented in Minion.
Peter Nightingale, Ian P. Gent, Christopher Jefferson, and Ian Miguel,
Short and Long Supports for Constraint Propagation,
Journal of Artificial Intelligence Research, Volume 46, pages 1-45, 2013.
Christopher Jefferson and Peter Nightingale,
Extending Simple Tabular Reduction with Short Supports (slides, poster),
in Proceedings of 23nd International Joint Conference on Artificial Intelligence (IJCAI), pages 573-579, 2013.
Peter Nightingale, Ian P. Gent, Chris Jefferson and Ian Miguel,
Exploiting Short Supports for Generalised Arc Consistency for Arbitrary Constraints, (slides, poster)
in Proceedings of 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 623-628, 2011.
Watched literals
Minion features ‘watched literals’, an implementation idea for constraints which has proved very successful in SAT. The following paper describes watched literals and other kinds of watched triggers for constraint propagation.
Ian P. Gent, Chris Jefferson, and Ian Miguel,
Watched Literals for Constraint Propagation in Minion, (slides)
in Proceedings of CP 2006.
Also available are slides from Chris Jefferson’s invited talk at the Constraint Propagation workshop at CP 2006.
Original Minion paper
The following paper describes a very early version of Minion, it is outdated in a number of ways. It was chosen as one of the ten best papers out of about 500 submissions to ECAI 2006.
Ian P. Gent, Chris Jefferson and Ian Miguel,
MINION: A Fast, Scalable, Constraint Solver, (slides)
in Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006).