[gecode-users] Weak points in Gecode

[Stefano Gualandi]

Dear Morten,

I am not an expert of BDDs, but maybe the paper below can help you:

http://www.cs.mu.oz.au/~pjs/papers/hawkins05a.pdf

The paper is about Reduced Ordered Binary Decision Diagrams (ROBDDs).  
Likely, you already know the paper...

It seems ROBDDs are good for constraints defined over set variables,  
as the partition constraints (implemented in Gecode as disjoint/union  
set operation), or the weighted sum constraints.

hope it helps.
Stefano


On Feb 3, 2009, at 9:13 PM, Morten Boysen wrote:

> 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