[gecode-users] Getting domain values after posting

[Efstratios Kalogirou]

Hi again,

I have used the status function to perform constraint propagation. After the
propagation I retrieve the values of the space to see if they are
consistent. This works fine with many constraints (mostly simple
cases) however there are other cases where the space is not reduced to the
consistent values only. I am working on large scale disjunctions of
conjunctions and I am interested in getting only the consistent values after
the propagation. A very simplified example is the following:
Three variables x1=[0..3], x2=[0..5], x3=[0..10] and a single constraint

(x1==0) && (x2==3) && (x3==7)  ||
(x1==0) && (x2==5) && (x3==9)

The constraint represents allowed values, so the above is read as:
x1 should be 0 and x2 should be 3 and x3 should be 7 or x1 should be 0 and
x2 should be 5 and x3 should be 9.

I would like to get the consistent values of the space after propagation,
which are for the first variable, the value 0, for the second variable the
values 3 and 5 and for the third variable the values 7 and 9. The value 1
for example belongs to the space of the first variable but it's inconsistent
because it doesn't satisfy the constraint.

I have written the following code for the above problem (q is an IntVarArray
of size 3):

    IntVar x1(this,0,3);
    IntVar x2(this,0,5);
    IntVar x3(this,0,10);
    q[0]=x1;
    q[1]=x2;
    q[2]=x3;
    int values1[3]={0,3,7};
    int values2[3]={0,5,9};

    BoolVarArgs firstConjunction(3);      //stores the BoolVar representing
each of the first 3 equalities
    BoolVarArgs secondConjunction(3);//stores the BoolVar representing each
of the last 3 equalities

    for(int i=0;i<3;i++)
      {
        //wraps each equality of the first conjunction in a single BoolVar
        BoolVar temporar(this,0,1);
        rel(this,q[i],IRT_EQ,values1[i],temporar);
        firstConjunction[i]=temporar;

        //wraps each equality of the second conjunction in a single BoolVar
        BoolVar temporar2(this,0,1);
        rel(this,q[i],IRT_EQ,values2[i],temporar2);
        secondConjunction[i]=temporar2;
      }
    BoolVar result1(this,0,1);
    BoolVar result2(this,0,1);
    BoolVar disjunction(this,0,1);

    bool_and(this,firstConjunction,result1);
    bool_and(this,secondConjunction,result2);

    bool_or(this,result1,result2,disjunction);

    post(this,disjunction==1);


    //performing propagation and getting the status report
    unsigned int alt;
    (void) status(alt);
    IntVarValues ranger(q[0]);
    while(ranger())
      {
        cout<<"The value is "<<ranger.val()<<endl;
        ++ranger;
      }


The status report says that the problem is solved and gives me the solution
0,3,7 but the retrival of the values of the space for the first variable
still contains the incosistent values 1,2,3. If I didn't have the
disjunction and I had only the constraint:
(x1==0) && (x2==3) && (x3==7)
the space would be successfully reduced to the consistent value 0 only.


I am assuming that Gecode depending on the nature of the constraint
sometimes reduces the space by removing inconsistent values, and other times
it doesn't. If that's the case I am wondering if there is a way to reduce
the space without me manually assigning a value to each variable,
then performing propagation, getting the report and removing that value from
the space of the variable if the propagation has failed.

Best,

Stratos

On 3/28/06, Christian Schulte <schulte at imit.kth.se> wrote:
>
> Hi,
>
> propagation in Gecode is not automatic (some simple cases are done
> immediately as you report, others are not). This is not a bug but an
> essential feature (this is what enables batch recomputation). In order to
> actually perform constraint propagation one has to invoke the
> status(unsigned int&) member function of a space. Not only will that
> perform
> constraint propagation but it also reports about the status of a space: is
> it failed, solved, does it require branching. So in your case just add
> something along the lines:
>        unsigned int alt;
>        (void) status(alt); // Discard status result
>
> After that you will be able to observe the result of constraint
> propagation.
>
> Christian
>
>
> --
> Christian Schulte, http://web.imit.kth.se/~schulte/
>
>
>
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
> Of Efstratios Kalogirou
> Sent: Tuesday, March 28, 2006 5:35 PM
> To: users at gecode.org
> Subject: [gecode-users] Getting domain values after posting
>
>
> Hi all,
>
> I am trying to get the remaining (valid) values and the size of the domain
> of a variable after posting some constraints (assuming that due to the
> constraints some values inside the domain are no longer valid). It seems
> that everything is fine when I don't use any BoolVar to wrap the
> contraint.
> For example:
>
> IntVarArray q(this,1,0,10);
> post(this,q[0]==3);
> cout<<"The size of the domain is now "<<q[0].size()<<endl;
>
> In the above case the size of the domain is indeed 1 and the solution is
> correctly the value 3.
>
> But things are different when I try to wrap the equality constraint in a
> BoolVar:
>
> IntVarArray q(this,1,0,10);
> BoolVar wrapper(this,0,1);
> rel(this,q[0],IRT_EQ,3,wrapper,ICL_BND);
> post(this, wrapper==1);
> cout<<"The size of the domain is now "<<q[0].size()<<endl;
>
> In the latter example I get again the corrent solution 3 but after posting
> the constraint the size of the domain remains 11 and doesn't shrink to 1
> as
> I would expect.
>
> Since I am solving problems using the second way I am wondering if there
> is
> a way to shrink the domain of the variable after posting as showed in the
> second example. Also how can I get all the valid values of the domain of a
> variable after posting? I assume this can be done by using iterators but I
> am not certain how exactly to relate the iterator with the IntVar or the
> IntSet that represents the variable, so any enlightening on that, would be
> highly appreciated.
>
> Best,
> Stratos Kalogirou
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20060329/e78d6d5d/attachment.htm>