[gecode-users] implementing branching heuristics

[Oliver Kullmann]

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/