[gecode-users] implementing branching heuristics

[Christian Schulte]

Hi,

please have a look at some of the examples that come with Gecode, there you
find how branch (which in turn creates simple variable/value branchings) is
used with different heuristics. There are two examples (black-hole.cc and
queen-armies.cc) that have simple custom branchings which might give you
some additional hints.

The current trunk has more support for predefined branchings (randomized,
tie-breaking, etc) that should make it into Gecode 3.* (scheduled to be
released around Sep/Oct). 

All the best
Christian

--
Christian Schulte, www.ict.kth.se/~cschulte/


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Oliver Kullmann
Sent: Friday, June 06, 2008 9:55 PM
To: users at gecode.org
Subject: [gecode-users] implementing branching heuristics

Hello,

based on my general theory of branching heuristics,
I would like to take some standard backtracking CSP solvers,
where I can just replace the variable ordering heuristics
(responsible for choosing the branching variable),
and there I would like to plug-in my generic
heuristics instead --- I expect relevant
performance gains.

The whole theory has been developed in the context
of SAT, but it is applicable for any width of
branchings (not just binary branchings), and this
is actually one of its strengths.

If somebody wants to read about it, please have
a look at report #7 at

http://www.swan.ac.uk/compsci/research/reports/2008/index.html 

It should be fairly easy to apply my generic heuristics.
I looked a bit at Minion, but this looks too much
black-box to me.

I guess in principle with gecode it should be doable.
But the documentation is rather terse, and I also
couldn't find some standard solvers, where I just
would replace some functions regarding the heuristics.

Perhaps somebody can help me here?
Or, if somebody is interested, we could have a collaboration.
I actually expect a "quick victory", i.e., it should
be quickly implementable, and it should yield some
nice improvements under fairly general circumstances.

So, I hope somebody is interest in a 
quick paper which will revolutionise CSP ;-)
Actually, I think it will be interesting.

Oliver

P.S. Another field for possible collaboration
would be library development: I am developing
the OKlibrary (http://www.ok-sat-library.org),
a generative library for generalised SAT solving.
In principle the OKlibrary covers also CSP,
but I'm yet "pre-alpha" :-(.

P.S.P.S. I noticed in the documentation
of gecode that "branchings" etc. are
used in a from my point of view somewhat
non-standard sense. I'm using "branching"
etc. as used by the SAT community and as
explained in my article, but this seems to
me also compatible to the notions used
in the Handbook of Constraint Satisfaction.

-- 
Dr. Oliver Kullmann
Computer Science Department
Swansea University
Faraday Building, Singleton Park
Swansea SA2 8PP, UK
http://cs.swan.ac.uk/~csoliver/

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