Access propagator from user-defined value selection function

[John]

Dear Gecode community

I am writing a custom propagator. During each propagation, the propagator is able to determine which value is best to branch on next, for each different variable. These values are computed for free, as part of the constraint consistency check, and are saved within the propagator. I'd like to use them as a heuristic. However, I am not sure how to correctly gain access to the propagator in the current space (to get the best values), from within a user-defined value selection function. What is the best way to achieve this, or is there a different approach?

[Mikael Zayenz Lagerkvist]

Hi,

The real answer for managing state shared between actors in Gecode
(propagators and branchers) that coexist in a single space is to
create a local object and handle managing that state. How to do this
is described in chapter 31.4 in Modeling and Programming with Gecode.

However, as you indicate that you use a value-selection function, I am
guessing that your brancher is using the branch-family of functions
with a supplied function. As far as I know, there is no good way that
I know of to add custom state managed by a handle to it. If your
propagator and brancher are for a model and they are only supposed to
be used with that model, then the easiest solution is to store the
extra information as a member in Space for the model. update the data
in the propagator, read the data in the value selection function, and
copy the data in the copying constructor.

Cheers,
Mikael

> --
> 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/e083136f-2afa-405d-b158-2ba53ba0145an%40googlegroups.com.



--
Mikael Zayenz Lagerkvist

[John]

Thank you very much for the directions, I will look into it!

John

[John]

Hi,

Thank you for your initial response, I will give some more details on my specific use case.

Each time the propagator decides that the constraint is consistent, it manages to find a solution to the problem, given the current domains. The goal is to use that information to avoid unnecessary branching on wrong values by search, since we can go straight to a solution every time.

The propagator is not tied to a specific model, it is supposed to be independent and used by any model.

I am using a value-selection function in my demo model, but I don't have to, I just did because I thought this could have been one way to approach this. About the Local Object / Handle solution you mentioned, in order to integrate it, would I have to make a custom brancher?

[Mikael Zayenz Lagerkvist]

Hi John,

This sounds like the typical use-case of a Local Object and Handle.
For that you will need to make your own class for the brancher that
can handle copying and reference counting of the local object. The
best documented way is to write your own brancher by following the
relevant part in MPG.

Now, the existing family of branch-functions are not magic, and the
machinery can be re-used. Unfortunately it is not possible currently
to simply extend it with just a new INT_VAL_FOO(handle) function,
although that would be very nice to have. You could however look at
how it is implemented and construct the relevant parts on your own.
Some example parts of the code that you might want to take a look at
are
* Value selection objects:
https://github.com/Gecode/gecode/blob/develop/gecode/int/branch/val-sel.hpp
* Construction of the value selection objects:
https://github.com/Gecode/gecode/blob/develop/gecode/int/branch/val-sel-commit.cpp
* The actual brancher behind branch:
https://github.com/Gecode/gecode/blob/develop/gecode/int/branch.hh#L626

Hope this helps
Mikael

On Tue, Jul 6, 2021 at 5:02 PM 'John' via Gecode

> To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/4b932572-462b-454c-af73-7776cba4de54n%40googlegroups.com.



--
Mikael Zayenz Lagerkvist

[John]

Hi,

Thank you, that covers my questions. I have now implemented a custom brancher, 

and I'm using the Local Object and Handle with External Resources example, from the documentation. 

However I am do not fully understand the correct way to integrate it, since there is also no documented 

example of using it in practice. Can you give me some more details about things like, where should

the Local Handle(s) reside at? In the model/propagator/brancher?

Currently I have a Local Handle in the model, propagator, and brancher classes, and I update them

on the respective copy constructors. This is obviously wrong (after finding one solution, the propagator tries to write to free'd memory), 

as I haven't fully understood how to use it.

[Mikael Zayenz Lagerkvist]

Hi,

Yes, we should probably add a more detailed example for how to use
LcoalHandles, I agree. I think the biggest issue is coming up with a
good small example where it is useful.

In general, you should only store the handle in the objects that
actually need access to it. If I've understood your case correctly,
that should be in your propagator and in your custom brancher, but not
the model. This is so that if your brancher is done and the propagator
is entailed, the LocalObject will not be copied over to new clones.

As for your crashes, that seems to me like an issue in how you have
implemented your LocalObject. Do you create a new copy of the data
container (such as std::vector), or are you re-using the same data
container for all LocalObject isntances? If you could share the code
for it, it would be helpful in diagnosing your issue.

Cheers,
Mikael

On Tue, Jul 13, 2021 at 6:23 PM 'John' via Gecode

> To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/bb09c148-d4ef-4211-919f-b40b215ed0bfn%40googlegroups.com.



--
Mikael Zayenz Lagerkvist