[gecode-users] Optimizing the constraint

[Guido Tack]

Jeffrey wrote:

> I'm optimizing my constraints with Gist at the moment.

I assume you mean that you use Gist in Branch-and-Bound mode, using a  
constrain method in your model (or something similar to the  
MinimizeExample or MaximizeExample classes).

> I've found that there are lots of pruned tree on the left hand side.
> These trees may span up to 4-5 levels.
> Unfortunately, when I trigger gist to print out the dead node, I  
> didn't find any values that is making any constraints failed.

A value in a domain cannot make a constraint failed, only the absence  
of values can.

> I had tried to add implied constraints which had already improve the  
> speed for some cases.
>
> I'm currently using: INT_VAR_SIZE_MAX, INT_VAL_MIN   for branching  
> an IntVarArray.
>
> (1) What problems may it be? Is there any dynamic implied constraint  
> in Gist?

There's nothing special in Gist, it does exactly the same search as  
the non-interactive branch-and-bound engine, it only visualizes the  
search tree in addition.  And I'm not sure what you mean by "dynamic"  
implied constraint, but there's no magic going on.  The constraints  
are the ones you specify in your model.

> (2) If I found that many dead node of a big pruned tree is found by  
> the last assignment of values, How can I make such assignment comes  
> earlier? e.g. Assign variables with more constraints first? Is it  
> possible for Gist?

Again, this has nothing to do with Gist.  You can branch over  
variables with more constraints first, this is called degree branching  
(see the documentation).

> (4) Although i use "INT_VAR_SIZE_MAX", it doesn't assign all values  
> at once. Is that a bug or i'm misunderstanding its use?

Please read the tutorial about branchings again (in the Search chapter).

> "INT_VAR_RND" is not suitable to me cause I want the search to be  
> deterministic.
> (5) Is there any other tricks I could use to sort out the problem?  
> e.g. Deleting the constraint one by one to see which constraint is  
> making it goes so long?

When you delete constraints, the search tree is going to get bigger.   
I thought your problem took too long to solve because the search tree  
was too big, so deleting constraints can't help.

> (6) Is there another symthoms i should try to look at the gist tree  
> to get hint about the problem? e.g. what propagation setting should  
> it be.

What you can do is to look at a node and determine if you can do any  
additional inferences by hand (i.e., if you know that certain values  
shouldn't be in a variable domain any more because of some  
constraint).  That might give you an idea which propagator is missing  
or should be stronger.

I'm afraid your problems are more related to general constraint  
programming questions rather than specific to Gecode.  You may want to  
read more introductory material to the field first.

Cheers,
	Guido