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: [email protected] [mailto:[email protected]] On Behalf Of Morten Boysen Sent: Tuesday, February 03, 2009 10:14 PM To: [email protected] 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 [email protected] https://www.gecode.org/mailman/listinfo/gecode-users _______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
