[gecode-users] Weak points in Gecode

[Christian Schulte]

Nope, you will have to throw a really large number at it. To bring it down,
definitely more than 100 000, better more than a million (we regularly run
stupid benchmarks for scalability, so that's not even guessing). Also,
recomputation gives Gecode quite an edge here.

What might work are lots of small constraints that take some memory. As it
comes to binary constraints the one that uses more memory than others is the
element constraint with large arrays. But, there the BDD will explode
because you need large domains for that to be meaningful. Maybe mid-size
domains and lots of element constraints could be something.

Christian

--
Christian Schulte, www.it.kth.se/~cschulte/

-----Original Message-----
From: Morten Boysen [mailto:boysen at itu.dk] 
Sent: Wednesday, February 04, 2009 8:03 PM
To: Christian Schulte
Cc: 'Stefano Gualandi'; users at gecode.org
Subject: Re: [gecode-users] Weak points in Gecode

Hi,

Another problem is that our models only include boolean and integer 
variables, so the set variables will unfortunately not work.

Do you have any other suggestions? For example, how does Gecode perform 
with a very large amount of binary constraints? Can Gecode be 
overwhelmed by the shear amount of propagators?

Kind regars
Morten Boysen

Christian Schulte skrev:
> Well, that might be considered cheating: Gecode features complete set
> variables (CpltSetVar as opposed to SetVar) that actually implement the
idea
> from the paper Stefano mentions.
> 
> 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 Stefano Gualandi
> Sent: Wednesday, February 04, 2009 5:41 PM
> To: Morten Boysen; users at gecode.org
> Subject: Re: [gecode-users] Weak points in Gecode
> 
> 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
> 
> 
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>