Custom branching on set variables

[John]

Hello,

I have a custom propagator that deals with Int variables, and each time it is executed, it is able to calculate useful heuristic information about which value to branch on next, for each variable. I forward this information to a custom brancher using a Local Object Handle, and I branch on them. Everything works as expected. 

Now I am making a similar propagator, with the difference that it deals with Set variables instead. Say that we have two variables, each time it is executed, it gives heuristic information in the form "Variable x0 should be assigned to set {a, b, c} and variable x1 should be assigned to set {b, d}". However, from my understanding, branching on equality and unequality to a specific set is not possible with this data type, as instead we should either include or exclude an element from the bounds of the set. Is there any way that I could approach it to take advantage of this heuristic information, or is it not compatible with Sets?

Thank you

[Mikael Zayenz Lagerkvist]

Hi John,

Nice to hear that you've gotten the local object handle to work for
sharing information.

You can definitely make that type of branching for set variables. For
SetViews, the list of domain updates in [1] under "Domain update
by..." includes the method intersectI, that intersects the domain with
athe values from an iterator. See chapter 26.2 in MPG for more details
on iterators and domain updates.

In general, while the vast majority of branchers make choices that are
of the type either x=v or x!=v for a variable x and some value v, this
is not the only type of branching that can be done. The commit
function in a brancher can in reality do more or less whatever it
wants, including posting any kind of additional propagator that can be
required. A typical case could be a scheduling problem where a
branching decision might be to add either t1 < t2 or t2 < t1 as
orderings for two tasks.

Cheers,
Mikael

[1] https://www.gecode.org/doc-latest/reference/classGecode_1_1Set_1_1SetView.html

> --
> 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/8edc2885-46f6-4b58-9d1e-605bcba0996bn%40googlegroups.com.



--
Mikael Zayenz Lagerkvist

[John]

Thank you for your response!

I have already come across the intersectI method, but I am not sure how I can use it to achieve what I need. 

Assume that variable x0 is defined as follows:

GLB: {}

LUB: {a, b, c, d}

cardMin: 0

cardMax: 4

and that my heuristic says that I should branch it on the set {a, b, c}. 

I would like to create two branching choices, one that assigns x0 specifically to {a, b, c}, 

and one that removes just the element {a, b, c} from its domain. 

For the first case, I can make the GLB equal to {a, b, c} and set cardMax to 3.

What would I do for the second case? I can't achieve it by reducing the LUB and/or cardMax,  

because that would result in removing more values than the one I want.

[Mikael Zayenz Lagerkvist]

Hi,

Yes, that is a relevant question. The easy answer is to use the
constraint dom(home, x0, SRT_NQ, {a, b, c}) (see [1]) for the right
hand side. This is exactly what you describe, but it is also not very
good as it will most likely not propagate anything immediately. The
reason is that the set variable domain used in Gecode (and in most
constraint programming systems) is not detailed enough to record that
particular information. If you aren't careful, the brancher might even
end up re-trying the same decision again with the left decision
failing immediately and the right just creating a duplicate
propagator. The simple way to avoid re-trying the same decision is to
record the decisions made in the brancher and avoid making it again.

In general, the goal of a brancher is to partition the search space:
the alternatives created should be disjunct but also cover all
alternatives. In practice, the result of a decision by a brancher
should be reflected in the domains in some way, since otherwise there
is no new information derived from propagation.

I would say what you do depends on the particulars of your problem.
Try to see if there is something that you can say for the right hand
side that works for your problem that can be exploited. In the worst
case, you could also try an n-way branching with all the alternatives
that are not the first one enumerated:

x0={a, b, c}, (a in x0, {b, c} not in x0), ({a, b} in x0, c not in
x0), (b in x0, {a, c} not in x0), ...

while this would work, my guess is that it would be quite bad for the search.

Cheers,
Mikael

[1] https://www.gecode.org/doc-latest/reference/group__TaskModelSetDom.html#ga8b5263e1bef81c11e4ba9889f0f26568

On Wed, Jul 13, 2022 at 6:32 PM 'John' via Gecode

> To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/17a92087-1b25-415c-8958-5c341130073en%40googlegroups.com.



--
Mikael Zayenz Lagerkvist