Learn MiniCP

This tutorial is based on the course “LINFO2365 Constraint Programming” given at UCLouvain by Pierre Schaus.

Outcomes

Learning outcomes by studying MiniCP:

From a state and inference perspective, specific learning outcomes include:

  • Trailing and state reversion

  • Domain and variable implementation – Propagation queue

  • Arithmetic Constraints

  • Logical Constraints

  • Reified Constraints

  • Global Constraints (including for scheduling)

  • Views

From a search perspective, the outcomes include:

  • Backtracking algorithms and depth first search

  • Branch and Bound for Constraint Optimization

  • Incremental Computation

  • Variable and Value Heuristics implementation

  • Searching with phases

  • Large Neighborhood Search

While, from a modeling perspective, the outcomes include:

  • Redundant constraints

  • Bad smells and good smells: model preferably with Element constraints instead of 0/1 variables

  • Breaking symmetries

  • Scheduling: producer consumer problems, etc.

  • Design problem specific heuristics and search

MiniCP Article

The complete architecture of MiniCP is described in this paper (publisher PDF) (errata and delta with current source code of MiniCP):

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