Mini-C++

A C++ CP Solver that implements the MiniCP API. The architecture is identical to that of MiniCP and can be found in the paper MiniCP: A lightweight solver for constraint programming published in Mathematical Programming Computation and best cited as

@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}}

The github repository is for miniC++ is here.

Customary n-Queens

The classic n-queens model is as follows

#include <iostream>
#include <iomanip>
#include "solver.hpp"
#include "trailable.hpp"
#include "intvar.hpp"
#include "constraint.hpp"
#include "search.hpp"

int main(int argc,char* argv[])
{
    using namespace std;
    using namespace Factory;
    const int n = 12;
    CPSolver::Ptr cp  = Factory::makeSolver();
    auto q = Factory::intVarArray(cp,n,1,n);
    cp->post(Factory::allDifferentAC(q));
    cp->post(Factory::allDifferentAC(Factory::intVarArray(cp,n,[q](int i) {
                                                                  return q[i] + i;
                                                               })));
    cp->post(Factory::allDifferentAC(Factory::intVarArray(cp,n,[q](int i) {
                                                                  return q[i] - i;
                                                               })));

    DFSearch search(cp,firstFail(cp,q));
    auto stat = search.solve();
    cout << stat << endl;
    cp.dealloc();
    return 0;
}

This model uses 3 global constraints to model the all different requirements and implements the search as a call to the provided first-fail heuristic (variable with the smallest domain first). Following the miniCP style, the search can be implemented from first principles as follows

DFSearch search(cp,[=]() {
                      auto x = selectMin(q,
                                         [](const auto& x) { return x->size() > 1;},
                                         [](const auto& x) { return x->size();});
                      if (x) {
                         int c = x->min();
                         return  [=] { cp->post(x == c);}
                               | [=] { cp->post(x != c);};
                      } else return Branches({});
                   });

Indeed, the search first selects a variable from the q array whose domain size is greater than 1 but as small as possible. That variable is bound to the name x. If such a variable exist, the closure returns a branching for it that either binds x to the smallest value in its domain, or alternatively, prohibits variable x from ever being equated to c. If no variable x exist that meet the criteria in the selectMin, then all variables are bound and the closure returns an empty branching.

MiniC++ and its extensions

Mini C++ can model quite a few classic CP problems. But it also comes with several extensions that are worth mentionning

Haddock

Mini C++ is the substrate for the implementation of Haddock, the MDD-based propagator for many globals.

GPU

Mini C++ was used to implement GPU based global propagators.

• CP