[gecode-users] How does Gecode works ?

[Guido Tack]

Debdeep Banerjee wrote:

> Hi,
>  I am just wondering how gecode works. What I think is the following
>
> 1. We create the variables and domains
> 2. Then we post constraints
> 3. Then we define the branching
> 4. We start searching. ( I am here referring to the DFS search)
>       1. the search will do the propagation, if any inconsistency  
> found
> then fail immediately
>       2. then branching will produce a variable-value pair through the
> description() method
>       3. then commit() will produce a binary branching
>             a. variable = value , left
>             b. variable != value. right
>       4. the search will continue picking up the left branch and call
> the propagation method, if failed, it will try the right branch.
>
> Is this correct ?

Yes, that's the overall picture.

> My questions are
> 1. When we post constraints, for example
>    rel <cid:part1.05040408.08010402 at rsise.anu.edu.au>(Space
> <cid:part2.09030509.04060200 at rsise.anu.edu.au>* home, IntVar
> <cid:part3.07050402.03060701 at rsise.anu.edu.au> x0, IntRelType
> <cid:part4.09080505.00030106 at rsise.anu.edu.au> r
> <cid:part5.06050303.09070201 at rsise.anu.edu.au>, int n
> <cid:part6.06090502.08060905 at rsise.anu.edu.au>, IntConLevel
> <cid:part7.01060008.08080700 at rsise.anu.edu.au>, PropKind
> <cid:part8.07080100.00090002 at rsise.anu.edu.au>)
>    Does gecode create any propagator for this ? I have looked at the
> rel.cc file the implementation, but it seems like it doesn't create  
> any
> propagator. How does it get called from space->status() ??

Basic constraints that can be immediately represented in the variable  
domains are not implemented as propagators.  You can observe the  
difference easily: when you do post(this, x >= 4), all values less  
than 4 will be immediately removed, even without calling status.

> 2. When I execute the following code
>    x.eq <cid:part9.00000207.03050104 at rsise.anu.edu.au>(home,n) ==> x  
> is
> IntView and n is an Integer.
>    is the variable ( IntVar ) that the x refers to, is assigned to 'n'
> immediately ? or it will be assigned when space->status() method is  
> called ?

It is assigned immediately.  In fact, all operations on views have an  
immediate effect on the domains, they never post propagators.  Note  
that eq returns a ModEvent, which tells you what kind of modification  
happened.  You have to check this, and if it signals failure, you are  
responsible for reporting that failure.  That's why these operations  
are only available for views, which are used in propagators and  
branchings.  The variables you use for modelling do not have these  
domain update operations, but you have to call them through the  
appropriate post functions (like rel), which handle failure correctly.

> I am sorry if these questions are too basic. I am trying to understand
> how gecode works a bit more thoroughly.

No problem, you're very welcome to ask basic questions.

Cheers,
	Guido