[gecode-users] counting-based search in Gecode

[Gilles Pesant]

I would like to integrate counting-based branching heuristics in Gecode. Like AFC we need to collect information from each constraint in which a given variable appears. But our information is more involved than a simple updated failure count --- we have dedicated algorithms computing "solution densities" for variable-value pairs. We saw that we can define a Brancher to make an integrated choice of both variable and value. But to host our solution counting code we see two options:

1) In objects of a class Counter which, like Propagator, would inherit from Actor and subscribe to variables. They would mainly implement a getSolutionDensity(var,val) method and possibly react to domain events by updating data structures (via Advisors?).

2) By inheriting directly from Propagator, say in a class CountablePropagator, which may allow us to share data structures used by the propagator: for example for the regular constraint the layered graph is augmented with counters of incoming and outgoing paths at nodes.

What's your opinion?

Thanks,
Gilles