[gecode-users] Weak points in Gecode

[Morten Boysen]

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