[gecode-users] counting-based search in Gecode

[Christian Schulte]

Hi Gilles,

That sounds really interesting, very nice!

I would never go for 1): This would require you to change things inside the
Gecode kernel. This will most likely be a very frustrating experience. Even
I would not dare doing that unless I had half year and under the assumption
that I know Gecode as well as I do already.

2) sounds more promising but still very ambitious.

If I were you, I would have a look at how activity information is recorded
(the files are in gecode/kernel). The idea is as follows: a propagator is
created which does not really do any propagation but it just records
information about how variables change. To make it efficient this propagator
is given a very high cost so that it will run only after all "real"
propagators have reached their fixpoint. And as you suggest it uses advisors
to do that. My gut feeling is that you can start very quickly from what is
already there for activity recording.

It is not that obvious how to share datastructures then. It is possible in
principle, though. But I'd really leave that to later.

Cheers
Christian

--
Christian Schulte, www.gecode.org/~schulte 
Professor of Computer Science, KTH, cschulte at kth.se
Expert Researcher, SICS, cschulte at sics.se

-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Gilles Pesant
Sent: Saturday, February 13, 2016 02:23 AM
To: users at gecode.org
Subject: [gecode-users] counting-based search in Gecode

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

_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users