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

There is an EdX MOOC Constraint Programming but all the videos and programming exercises are now available freely from this page.

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.

Exercises and Assessment

For each module, participants are required to complete:

  • Programming Exercises: Hands-on implementation of solver components and models in MiniCP.

  • Reasoning Exercises: Short theoretical questions and puzzles to test your understanding of the concepts.

All exercises and project submissions are managed through the INGInious platform: Access the Exercises

Videos

00: Course Trailer

  • Link: Trailer

  • Summary: A brief introductory video providing an overview of the course goals and what participants can expect to learn about Constraint Programming.

01: CP Intro and Tiny CSP

  • Link: Video Playlist

  • Slides: 01-intro-cp.pdf

  • Summary: Introduces the foundations of CP using the N-Queens problem. It progresses from a basic “generate and filter” approach to early failure detection, and finally to the implementation of Tiny-CSP. Key concepts include fix-points, domains, state restoration, and declarative programming. It concludes with an introduction to the graph-coloring problem.

02: Mini-CP Internals

  • Link: Video Playlist

  • Slides: 02-minicp-architecture.pdf

  • Summary: Explores the “dark side” or internal architecture of a real CP solver. Topics include the implementation of efficient sparse-set domains, variable change notification, the fix-point engine, and Depth-First Search (DFS). It also covers critical state-restoration mechanisms like trailing and the StateManager.

03: Implementing Constraints

  • Link: Video Playlist

  • Slides: 03-sum-element-constraint.pdf

  • Summary: Focuses on the design and implementation of core constraints. It distinguishes between Domain and Bound consistency and examines specific constraints like Sum and Element (1D and 2D). Additional topics include idempotency, variable views, boolean variables, reified/logical constraints, and their application to problems like Stable Matching.

04: Table Constraints

  • Link: Video Playlist

  • Slides: 04-table-constraints.pdf

  • Summary: Dedicated to the Table constraint, the most flexible constraint in CP capable of modeling any relationship. The module covers practical applications like the Eternity II puzzle and automata-based modeling, as well as high-performance filtering algorithms such as STR and Compact-table.

05: AllDifferent Constraint

  • Link: Video Playlist

  • Slides: 05-alldifferent.pdf

  • Summary: Analyzes one of the most famous global constraints. It covers simple decomposition methods, faster filtering heuristics, and the advanced graph-based algorithm used to achieve full Domain Consistency.

06: Routing and Optimization

  • Link: Video Playlist

  • Slides: 06-circuit-optim-lns.pdf

  • Summary: Transitions into optimization and Vehicle Routing Problems (VRP). It details the Circuit constraint, including subtour elimination. It also introduces Large Neighborhood Search (LNS), a powerful technique for finding high-quality solutions quickly.

07: Cumulative Scheduling

  • Link: Video Playlist

  • Slides: 07-cumulative-scheduling.pdf

  • Summary: Explores scheduling through the Cumulative constraint. It covers feasibility checking using the sweep-line algorithm, updating activity time windows (time-table filtering), and applications in producer-consumer and packing problems.

08: Disjunctive Scheduling

  • Link: Video Playlist

  • Slides: 08-disjunctive-scheduling.pdf

  • Summary: Focuses on resources with a capacity of one (disjunctive resources), as seen in the Jobshop problem. It introduces the Theta tree data structure to implement efficient filtering algorithms like Overload Checker and Not-Last.

10: Advanced Modeling

  • Link: Video Playlist

  • Slides: 10-modeling-symmetries.pdf

  • Summary: Covers the “art” of modeling, featuring the Bin-Packing and Steel Mill Slab problems. Topics include symmetry breaking, redundant constraints, and the watched literal technique. It also introduces modeling languages like MiniZinc and PyCSP3.

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.

Pierre Schaus is Professor at UCLouvain.

Laurent Michel is Professor at the University of Connecticut.

Pascal Van Hentenryck is Professor at Georgia Tech.