MiniCP: A lightweight Constraint Programming Solver

What is MiniCP

The success of the MiniSAT solver has largely contributed to the dissemination of (CDCL) SAT solvers. The MiniSAT solver has a neat and minimalist architecture that is well documented. We believed the CP community was missing such a solver that would permit newcomers to demystify and learn the internals of CP technology. Therefore we developped MiniCP, a white-box bottom-up teaching framework for CP implemented in Java. MiniCP is voluntarily missing many features that you would find in a commercial or complete open-source solver. The implementation, although inspired by state-of-the-art solvers, is not focused on efficiency but rather on readability to convey the concepts as clearly as possible. MiniCP is small and well tested.

Learn MiniCP and Constraint Programming

The best way to learn MiniCP is to subscribe to our EdX MOOC Constraint Programming

In this course, we will learn, using MiniCP, the basics of constraint programming: a paradigm that aims to reduce the cost of developing and solving combinatorial problems through extensive reuse of code, whose design is open-ended, but also through pruning techniques of the search space by reasoning at the level of constraints.

During the proposed projects, you will extend MiniCP in functionality in order to solve more and more complex combinatorial problems, especially in scheduling and vehicle routing. You will also develop global constraints, implement search strategies, model problems, and measure the impact of modeling choices on the efficiency of the solution.

Each of the 10 modules first introduces the concepts through videos, then a programming project is proposed to put these concepts into practice.

MiniCP Article

The complete architecture of MiniCP is described in this paper (publisher PDF) (errata and delta with current source code of MiniCP). Please cite this paper if you use MiniCP in one of your article or if you get inspiration of it.

 1@article{cite-key,
 2        Author = {Michel, L. and Schaus, P. and Van Hentenryck, P.},
 3        Doi = {10.1007/s12532-020-00190-7},
 4        Id = {Michel2021},
 5        Isbn = {1867-2957},
 6        Journal = {Mathematical Programming Computation},
 7        Number = {1},
 8        Pages = {133-184},
 9        Title = {MiniCP: a lightweight solver for constraint programming},
10        Ty = {JOUR},
11        Url = {https://doi.org/10.1007/s12532-020-00190-7},
12        Volume = {13},
13        Year = {2021}}

Javadoc and Github Repository

Getting Help with MiniCP

You’ll get the greatest chance of getting answers to your questions by using the MiniCP usergroup.

Who Uses MiniCP?

If you use it for teaching or for research, please let us know and we will add you in this list.

  • EdX MOOC, INGI2365, teachers: Pierre Schaus, Laurent Michel, Pascal Van Hentenryck.

  • UCLouvain, Belgium, INGI2365, teacher: Pierre Schaus.

  • Uppsala University, Sweden, course 1DL442, teacher: Pierre Flener.

  • ACP, Summer School 2017, Porquerolles, France, teacher: Pierre Schaus.

  • ACP, Summer School 2019, Vienna, Austria, teacher: Pierre Schaus.

About

Laurent Michel is Professor at the University of Connecticut.

Pierre Schaus is Professor at UCLouvain.

Pascal Van Hentenryck is Professor at Georgia Tech.