Recommended way of requesting propagation

[Luis Quesada]

Dear all,

I am pretty sure I am making a pretty silly mistake. My apologies in advance.  

I am referring to Tip 2.2 (Page 19 of MPG), which  says that one  should use m->status to request propagation.

I have the skeleton of a propagator I am implementing below. I have just left the relevant part needed to reproduce the unexpected behaviour. I was expecting Dom::propagate to be executed, but it is not. However, if I post the constraint in line 79, it is executed… My question is:

(a) why do I need an additional constraint?

BTW, 

(b) My understanding is that I don’t need to subscribe the third argument of my propagator as it is a constant, am I right?

Thanks a lot in advance for your answer!

Cheers,

Luis

#include <gecode/int.hh>

#include <gecode/search.hh>

#include <iostream> // for std::cout

#include <utility> // for std::pair

#include <algorithm> // for std::for_each

using namespace std;

using namespace Gecode;

class Dom : public Propagator

{

protected:

ViewArray<Int::BoolView> G;

ViewArray<Int::BoolView> D;

int s;

public:

// posting

Dom(Space &home, ViewArray<Int::BoolView> &_G, ViewArray<Int::BoolView> &_D, int _s)

: Propagator(home), G(_G), D(_D), s(_s)

{

G.subscribe(home, *this, Int::PC_BOOL_VAL);

D.subscribe(home, *this, Int::PC_BOOL_VAL);

}

static ExecStatus post(Space &home,

ViewArray<Int::BoolView> G, ViewArray<Int::BoolView> D, int s)

{

(void)new (home) Dom(home, G, D, s);

return ES_OK;

}

// disposal

virtual size_t dispose(Space &home)

{

G.cancel(home, *this, Int::PC_BOOL_VAL);

D.cancel(home, *this, Int::PC_BOOL_VAL);

(void)Propagator::dispose(home);

return sizeof(*this);

}

// copying

Dom(Space &home, Dom &p)

: Propagator(home, p)

{

G.update(home, p.G);

D.update(home, p.D);

}

virtual Propagator *copy(Space &home)

{

return new (home) Dom(home, *this);

}

// cost computation

virtual PropCost cost(const Space &, const ModEventDelta &) const

{

return PropCost::binary(PropCost::HI);

}

// re-scheduling

virtual void reschedule(Space &home)

{

G.reschedule(home, *this, Int::PC_BOOL_VAL);

D.reschedule(home, *this, Int::PC_BOOL_VAL);

}

// propagation

virtual ExecStatus propagate(Space &home, const ModEventDelta &)

{

std::cout << "dom propagate\n";

return ES_NOFIX;

}

};

class testDom : public Space

{

protected:

BoolVarArray l;

public:

testDom(void) : l(*this, 100, 0, 1)

{

//rel(*this, BoolVar(l[0]), IRT_EQ, 0);

BoolVarArgs _foo(l);

dom(_foo, _foo, 1);

//branch(*this, l, BOOL_VAR_NONE(), BOOL_VAL_MIN());

}

// search support

testDom(testDom &s) : Space(s)

{

l.update(*this, s.l);

}

virtual Space *copy(void)

{

return new testDom(*this);

}

void dom(BoolVarArgs _G, BoolVarArgs _D, int s)

{

ViewArray<Int::BoolView> G(*this, _G);

ViewArray<Int::BoolView> D(*this, _D);

if (Dom::post(*this, G, D, s) != ES_OK)

this->fail();

}

// print solution

void print(void) const

{

std::cout << l << std::endl;

}

};

// main function

int main(int argc, char *argv[])

{

testDom *m = new testDom;

(void)m->status();

m->print();

return 0;

}

[guido...@monash.edu]

Hi Luis,

propagators that subscribe only to VAL events are never executed unless at least one of those variables is fixed. This means that when propagate is called, you can be sure that at least one more variable is fixed than last time (so you don't have to check). That's why adding the extra constraint (which fixed a variable) causes propagation. If you want to do some initial propagation (no matter whether variables are fixed or not) you have to do that in the post method.

Cheers,

Guido

[Luis Quesada]

Hi Guido,

Thanks a lot for that. It makes a lot of sense. I got another questions that is  kind of orthogonal (and in fact I am not sure whether I should be asking this here in this list or in the MiniZinc one). Could you please elaborate on the role that 'AST::Node* ann’ play in the definition of p_distinct,  for instance?

I am not sure what to do for my particular constraint.

void p_distinct(FlatZincSpace& s, const ConExpr& ce, AST::Node* ann)

My propagator seems to be working fine. The plan is now to be able to use it from MiniZinc as I mentioned in my last message to MiniZinc.

BTW, is there any recommendation wrt the location where I should place the implementation of my constraint?

Thanks a lot for that!

Cheers,

Luis

--
You received this message because you are subscribed to the Google Groups "Gecode" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gecode+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/4fc3d023-9509-40e8-a70f-8ea2688b02a4n%40googlegroups.com.

[Mikael Zayenz Lagerkvist]

Hi Luis,

There can be many annotations passed to each registry post function,
but in the case of p_distinct, only ones related to propagation level
are checked for.

In particular, p_distinct calls the method ann2ipl which looks in the
annotations for occurrences of val, domain, and variations of bounds
to see if the model requests any particular level of propagation.

if your propagator has no special use ofr annotations, you can safely ignore it.

Cheers,
Mikael

> To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/A6FA168A-95DD-473C-BEB8-E46250923574%40insight-centre.org.



--
Mikael Zayenz Lagerkvist

[Luis Quesada]

Hi Mikael,
Thanks a lot for the explanation. I will ignore it then for the moment.
Cheers,
Luis

> To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/CAPKxCj7dPaDHM31Sc4BAp8LhOp88ivJFqYKUHWy_unpv4Z_kwA%40mail.gmail.com.

[Luis Quesada]

Dear all,

I am using boost in the implementation of my propagator. I can compile the propagator without any issue. I can also build the original fzn-gecode without any issue. However, I am not sure how to modify the original CMakeList.txt to include boost as I would like to have version of fzn-gecode containing my propagator (as some of you know). I naively thought it was something as simple as adding this line to CMakeList.txt:

include_directories(/usr/local/opt/bo...@1.75)

But it seems it is not that simple… Could you please let me know what I should do?

Thanks a lot in advance!

PS: Just for the records, I am using VS code. But I am not a VS code/C++ expert :-)

Cheers,
Luis

[Dekker, Jip J.]

Hi Luis,

I’m happy to hear propagator development is going well.

Before you start adding Boost as a dependency to Gecode I would suggest you first have a look if it really is required. Dependencies in C++ are generally hard to manage between different architectures/operating systems/machines. Not all systems will have the same libraries available and you almost never get the same version. This means you either will have to statically link the library into Gecode or distribute it with the specific library you need. In my experience of distributing MiniZinc, if you want to distribute your C++ application (which I assume you do if you want to merge the propagator into the Gecode repository), then you need to consider all alternatives before adding more dependencies when using C++.

Because you said you’re not a C++ expert, maybe you could share the functionality from Boost that you are using and maybe we can suggest an alternative from the C++ standard library. You could even have a look and see if you cannot include just a specific part of Boost directly in the Gecode source tree. This has already been done for some things: https://github.com/Gecode/gecode/tree/master/gecode/third-party/boost

If you really see no other way, then how to include Boost depends on the build system that you are using. Gecode uses autotools as its primary system and has a CMake configuration that reads parts for the former system.

I have little experience with adjusting the autotools system, but a quick search reveals that there exists a test for Boost: https://www.gnu.org/software/autoconf-archive/ax_boost_filesystem.html

In CMake I would suggest you use the Boost FindModule: https://cmake.org/cmake/help/latest/module/FindBoost.html

When Boost is found you should then be able to use

target_link_library(<gecode_target> Boost::<component>)

to link parts of Gecode against the Boost library.

I hope this helps,

– Jip

--
You received this message because you are subscribed to the Google Groups "Gecode" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gecode+un...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/2460AA25-45EE-4A3E-AF65-4973D9EBF351%40insight-centre.org.

[Luis Quesada]

Hi Jip,

Thanks a lot for this comprehensive answer. I will study it carefully and keep you posted.

Just to answer your question about what I am using from Boost, I am basically relying on these two includes:

#include <boost/graph/dominator_tree.hpp>
#include <boost/graph/transitive_closure.hpp>

Cheers,

Luis

To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/CAEjuCXMfWdjdcX3RPg6UAcifzF17cAneQpExPwMzhWwp9Ep2KQ%40mail.gmail.com.

[Luis Quesada]

Hi Jip, all,

First let me start by sharing the good news: thanks to your advice I was able to build the customised fzn-gecode. I commented out this line:

#include_directories(/usr/local/opt/bo...@1.75)

and added this instead:

find_package(Boost 1.75)
if(Boost_FOUND)
  include_directories(${Boost_INCLUDE_DIRS})
endif()

and this led to a successful build:

[…]

build] [100%] Linking CXX static library libgecodeflatzinc.a
[build] [100%] Built target gecodeflatzinc
[build] [100%] Linking CXX executable bin/fzn-gecode
[build] [100%] Built target fzn-gecode
[build] Build finished with exit code 0

insight086:bin lquesada$ /Users/lquesada/Gecode/gecode/build/bin/fzn-gecode
Usage: /Users/lquesada/Gecode/gecode/build/bin/fzn-gecode [options] <file>
       /Users/lquesada/Gecode/gecode/build/bin/fzn-gecode -help for more information

I have also managed to link the customised fzn-gecode to MiniZinc:

And if I leave the commented lines out, everything works as expected:

The problems start when I start uncommenting :-). First thing I noticed is that including gecode.mzn as done in Line 1 doesn’t work. Something that I tried was giving the full path to the one in the sources (as in line 2) and indeed that way it finds the file but I get this error:

I guess I have done something wrong in the registration of the constraint. Please let me tell you what I did:

(1) I added this line to gecode.mzn:

predicate gecode_dominators(array[int] of var bool: G, array[int] of var bool: D, int: src);

(2) I added this to registry.cpp

#include "domConstraint.hpp"

[…]

      void p_dominators(FlatZincSpace &s, const ConExpr &ce,
                        AST::Node *ann)
      {
        BoolVarArgs _G = s.arg2boolvarargs(ce[0]);
        BoolVarArgs _D = s.arg2boolvarargs(ce[1]);
        int _src = ce[2]->getInt();
        ViewArray<Int::BoolView> G(s, _G);
        ViewArray<Int::BoolView> D(s, _D);
        if (Dom::post(s, G, D, _src) != ES_OK)
          s.fail();
      }

[…]

registry().add("gecode_dominators", &p_dominators);

(3) Put the implementation of the propagator in domConstraint.hpp

Could you please tell where I went wrong?

Thanks a lot in advance!

Cheers,

Luis

On 10 Mar 2021, at 06:43, Dekker, Jip J. <j...@dekker.one> wrote:

To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/CAEjuCXMfWdjdcX3RPg6UAcifzF17cAneQpExPwMzhWwp9Ep2KQ%40mail.gmail.com.

[Jip J. Dekker]

Hi Luis,

My first indication would be to check if you are actually running the right Gecode executable. If you have to include the gecode file with an absolute path, then it sounds as if the solver configuration is incorrect. This might also mean that you are running the wrong fzn-gecode executable and if that is the case, then it is not unexpected for it to crash when it finds a constraint it doesn't know.

Otherwise it sounds like there is an issue somewhere in your version of fzn-gecode. The code you mention in your message sounds okay, but there are many places where things can go wrong. The easiest way to find the problem is to

1. Compile the MiniZinc model as you intend to use it (either using cmd + b in the IDE and saving the FlatZinc file or using the MiniZinc CLI: "minizinc --solver gecode -c some_model.mzn")

2. Now running "fzn-gecode some_model.fzn" should still give you the same error.

3. You can now create a debug mode of your version of fzn-gecode and use a debugger (like GDB or LLVM) to find your problem.

Cheers,

Jip

[Luis Quesada]

Hi Jip,

Let me see whether this is what I am getting wrong:

My first indication would be to check if you are actually running the right Gecode executable. If you have to include the gecode file with an absolute path, then it sounds as if the solver configuration is incorrect. This might also mean that you are running the wrong fzn-gecode executable and if that is the case, then it is not unexpected for it to crash when it finds a constraint it doesn't know.

Otherwise it sounds like there is an issue somewhere in your version of fzn-gecode. The code you mention in your message sounds okay, but there are many places where things can go wrong. The easiest way to find the problem is to

1. Compile the MiniZinc model as you intend to use it (either using cmd + b in the IDE and saving the FlatZinc file or using the MiniZinc CLI: "minizinc --solver gecode -c some_model.mzn")

I am following the advice that you gave me in one of your previous message where you told me to give to my custom gecode a different id/version number.  So in the line above I assume you mean “—solver mygecode”, isn’t it?

When I do this, this is the output that I get:

(Py39env) insight086:mznFoo lquesada$ minizinc --solver mygecode -c foo.mzn

/Users/lquesada/Documents/mznFoo/foo.mzn:1.1:

MiniZinc: error in include item, cannot open file 'gecode.mzn'.

(Py39env) insight086:mznFoo lquesada$ more ~/.minizinc/solvers/mygecode.msc

{

  "name" : "My Gecode",

  "version": "1.0",

  "id": "mygecode",

  "executable": "/Users/lquesada/Gecode/gecode/build/bin/fzn-gecode"

}

(Py39env) insight086:mznFoo lquesada$ more foo.mzn

include "gecode.mzn";

%include "/Users/lquesada/Gecode/gecode/gecode/flatzinc/mznlib/gecode.mzn";

array [0..24] of var bool: g;

array [0..24] of var bool: dg;

constraint gecode_dominators(g,dg,0);

solve satisfy;

When I comment out the include and the call to the constraint, it works just fine:

(Py39env) insight086:mznFoo lquesada$ minizinc --solver mygecode foo.mzn

g = array1d(0..24, [false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false]);

dg = array1d(0..24, [false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false]);

----------

Do you think the problem is in mygecode.msc? Regarding the process that I followed, I:

1 checked out the sources from the git repository

2 Opened the folder in VS code

3 Edited the files I mentioned in my previous message

4 Built the target from vs code, which created the executable /Users/lquesada/Gecode/gecode/build/bin/fzn-gecode

5 Created the mygecode.msc pasted above

BTW, I am using:

- macOS Big Sur

- MiniZinc 2.5.3

- Apple clang version 12.0.0

Cheers,

Luis

You received this message because you are subscribed to a topic in the Google Groups "Gecode" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/gecode/yD54sqlClhU/unsubscribe.
To unsubscribe from this group and all its topics, send an email to gecode+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/c3402de8-4d50-48be-8c54-cff174b9b149n%40googlegroups.com.

[Dekker, Jip J.]

Hi Luis,

It does indeed seem that the solver configuration calls the correct executable. The issue seems to thus be caused by a problem in the executable. Running ‘fzn-gecode’ with a debugger with the generated FlatZinc should point you to the problem.

The problem with the include-statement is, however, caused by you solver configuration. You are missing the “mznlib” key, which points MiniZinc to the correct MiniZinc globals library. This also means that MiniZinc would compile with the standard library and not with Gecode’s internal library. Because gecode supports most standard FlatZinc constraints this doesn’t give a problem however.

To solve this problem you might want to have a look at the Gecode configuration that is shipped with the MiniZinc bundle. You can find it in the bundle or in the MiniZincIDE repository: https://github.com/MiniZinc/MiniZincIDE/blob/master/resources/solvers/gecode.msc 

Cheers,

– Jip

To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/B003B44E-3B0D-4DE1-90C9-0302CBA1659D%40insight-centre.org.

[Luis Quesada]

Dear Jip et al,

Thanks again for your advice. Indeed I was missing this line in my configuration file:

"mznlib": "/Users/lquesada/Gecode/gecode/gecode/flatzinc/mznlib”,

Now it indeed finds gecode.mzn. I am now facing another problem though. The program below runs fine some times and crashes so other times as you can see below.

Anyway, I will follow your advice about using a debugger to find out what is going on. I will let you know when I make some progress. It will be slow though due to other duties.

One good thing is that this is not happening when I use Gecode directly. Still I will test exhaustively the propagator directly in Gecode to make sure the problem below has nothing to do with the propagator.

Cheers,

Luis

(Py39env) insight086:fznCase lquesada$ minizinc --solver mygecode foo.mzn

g = array1d(0..24, [false, true, true, true, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false]);

dg = array1d(0..24, [true, true, true, true, true, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true]);

----------

(Py39env) insight086:fznCase lquesada$ minizinc --solver mygecode foo.mzn

=====ERROR=====

(Py39env) insight086:fznCase lquesada$ more foo.mzn

include "gecode.mzn";

array [0..24] of var bool: g;

array [0..24] of var bool: dg;

constraint gecode_dominators(g,dg,0);

solve satisfy;

(Py39env) insight086:fznCase lquesada$

To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/CAEjuCXMTu%3DN_Nvy-wQxv0A6jhGnEqaRdrs9Yyjaop0XO5%3Dsx-A%40mail.gmail.com.

[Luis Quesada]

Dear all,

Just to say I found the issue. I was missing line 67 in my propagator  (i.e., copying the non cp variable).

I hadn’t actually tested the propagator during search.

Cheers,

Luis