The "connected" constraint from minizinc

[Andreas Lindmark]

I noticed that minizinc has a graph connectivity constraint which seems to work even when gecode is used as a backend, yet the MPG contains no mention of such a constraint.

I assume that minizinc converts the connected constraint to something that is equivalent to it before feeding it to gecode. Is this correct?

And while we're on this subject, there is a paper called "Reasoning about Connectivity Constraints" that provides an algorithm for efficient propagation of this particular constraint. Is there *any* interest for including an implementation of this algorithm in gecode? For example if I were to do it myself?

[Mikael Zayenz Lagerkvist]

Hi,

Sorry, I didn't see your message previously, so very late answer.

MiniZinc models are compiled for the solvers used, and when a constraint is not supported by the underlying solver,  a decomposition into simpler constraints is used. For connected, the final decomposition used after some steps is specified here: https://github.com/MiniZinc/libminizinc/blob/master/share/minizinc/std/fzn_dreachable_int.mzn

In general, we are very interested in contributions of new propagators for Gecode. We will require quite some care and lots of tests for a contribution, but it is a very fun programming exercise to write a propagator. The best start is to read the relevant chapters in Modeling and Programming with Gecode, to get a feel for how to implement a propagator in an idiomatic way. For testing, start by looking at some examples how it is done and asking for help here.

Cheers,

Mikael