Using non-local variable selection outside search engines

12 views
Skip to first unread message

Kish Shen

unread,
Jul 18, 2021, 5:28:42 PM7/18/21
to gec...@googlegroups.com
Hi,

Our ECLiPSe interface allows the user to do search at the ECLiPSe
level, i.e. outside of a searc

h , i.engine, and we provide a means to select a variable for branching.

Currently, for the non-local criterias, we support those using AFC and Action.

For AFC, we just get the AFC from IntVar.

For Action, we need to set up a IntAction object, and obtain the
action value via the object's [] operator.

It looks like I can do the same thing with IntCHB

The IntVarAction is initialised with a fix set of IntVarArgs, i.e. you
can't add new variables to it.

Are these limitations in Gecode 6.2? I tried looking to serif there
are any alternatives, but can't find anything in the reference
documentation. What were the reasons that IntAFC is available through
IntVar, but not for the other non-local selections?

Thanks and cheers,

Kish

Mikael Zayenz Lagerkvist

unread,
Jul 19, 2021, 4:05:37 AM7/19/21
to gec...@googlegroups.com
Hi Kish,

To give you some background, there are some crucial differences in how
AFC on one hand and Action and CHB are implemented. The latter two are
properties of individual variables with regards to propagations and
failures during search. They are implemented as AC_RECORD propagators,
which is a special priority level used for propagators that only
record information. AFC (accumulated failure count) is a property of
the summed behaviour of propagators subscribed to a variable - namely,
how many times they have triggered failure. This is not possible to
implement using a recording propagator, as the propagator and it's
advisors only know some of what has happened to a variable, not what
propagator triggered it. Thus, AFC is integrated more closely into the
Gecode architecture.

There is currently no easy way to dynamically extend the Action and
CHB information recorders. I'll think about if there is some good
workaround, but it probably highly depends on what the specific
requirements for your interface are.

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/CAHM-QAs29gMfdV3vRwve6o9NWESTqQ6skaCcN8mV1BY8V5Urqg%40mail.gmail.com.



--
Mikael Zayenz Lagerkvist

Kish Shen

unread,
Jul 19, 2021, 11:02:47 AM7/19/21
to gec...@googlegroups.com
Hi Mikael,

Thanks for your answer.

I think the only way our interface can make use of dynamically
extending Action and CHB is to allow every IntVar to use it, so I
suspect this will not be possible, from what you have said.

Is the difference between AFC and the others due to the way AFC is
implemented? I understand that AFC (or at least the weight part of
weighted degree) for a variable is the count of the number of failures
of constraints that the variable is involved in, but for the value of
the AFC for the variable, how is this different from counting the
number of failures during propagation that invlolve the variable? Is
it because you don't have AFC for each constraint (propagator) in the
counting variable failures case? If so, is the AFC for constraints
used in any of the (pre-defined) search engines?

Thanks and cheers,

Kish
> To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/CAPKxCj66%3DDb-kdbYncUgD2NRfZ6g6PtBPf3XXWM2QCrLr7yK0Q%40mail.gmail.com.

Mikael Zayenz Lagerkvist

unread,
Jul 20, 2021, 2:21:50 AM7/20/21
to gec...@googlegroups.com
Hi,

Yes, the difference is down to the way it is implemented. By
necessity, the AFC information is recorded internally, since it is not
possible to implement as a recording propagator. So it is not for
using it internally, it is to actually have the information available.
Action and CHB can be implemented purely as optional recording
propagators, and the kernel does not need to know anything about it.

In other words, the Gecode core records the failure counts for
propagators always and can be used for any variable, but one needs to
set up recording of Action and CHB for a variable ahead of the search
to get it.

Cheers,
Mikael
> To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/CAHM-QAudnO3H0j-78xu3w%3D1Pswzu18NOaejnd46qOqS%3DTveYsw%40mail.gmail.com.



--
Mikael Zayenz Lagerkvist
Reply all
Reply to author
Forward
0 new messages