[gecode-users] Weak points in Gecode
Christian Schulte
cschulte at kth.se
Wed Feb 4 16:18:57 CET 2009
Hi,
Well, well, I do spare you the details of the obvious answer ;-)
I though a little and have to say that I would have expected linear
arithmetic to be weak, where you really need reasoning about individual
values and not just bounds as Gecode does. But you basically tried that
already with Knapsack. (Also Gecode should suck at binomial). Table
constraints might work depending on the application.
So, honestly, no idea.
Sorry
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 Morten Boysen
Sent: Tuesday, February 03, 2009 10:14 PM
To: users at gecode.org
Subject: [gecode-users] Weak points in Gecode
Hi,
I have a somewhat odd request: I am looking for problem types that will
make Gecode perform poorly. First I will explain what we are trying to do:
Me and my thesis partner are writing a thesis about configuration, where
we are trying to do a hybrid between a configurator based on BDDs and a
solver. The reason for this is that certain types of constraints will
make a BDD perform very badly. An example of this is an Alldiff
constraint, which makes a BDD take up exponentially space. However,
other types of constraints are very well suited for BDDs and outperform
any search-based configurator, if the BDD can be build. Therefore, our
idea is to partition a problem, so the solver handles the Alldiff
constraint, whereas all other constraints are compiled into a BDD. This
BDD is then plugged into Gecode using a propagator. What we were hoping
for was to get the best of both worlds: The efficient Alldiff propagator
in Gecode, and the full inference of a BDD. However, out hybrid
configurator is having a hard time beating a purely search based
configurator, where all constraints are handled directly by Gecode.
What we therefore need, are some type of constraints that are well
suited for a BDD, but make Gecode behave in a pathological way. We have
tried knapsack constraints, binomial coefficients and we are now trying
with table constraints (also known as ad-hoc constraints). In all cases,
a pure Gecode configurator without a BDD propagator outperforms the
hybrid using a BDD (which by the way, shows how efficient Gecode is!).
Do you have any idea of any constraints that will make Gecode perform
poorly (e.g. by making it very hard for Gecode to do propagation, thus
resulting in a large search space).
Kind regards
Morten Boysen
_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
More information about the gecode-users
mailing list