[gecode-users] Expr() in GECODE

[Christian Schulte]

Hi Zichen,

 

Yes, you are right the minimodeling layer (that is expr()) should do a
better job at avoiding posting reified constraints if it is not necessary
(as you did in your own improved variants).

 

I'll write that down for a future release.

 

Let me try to explain what happens: with your first expression you create
three Boolean variables b1, b2, b3 and then three reified propagators:

                !_A[i] <=> b1

                (x[index] != val) <=> b2

                b1 || b2 = b3

and expr() returns b3. Unfortunately the constraints might stay on even
though the disjunction is already satisified (which it is in you example).
Embarrasingly enough, I am the co-author of a paper (done using Gecode) that
explains the problem and shows how to eliminate these constraints but it has
not yet made it into Gecode:

 
http://web.it.kth.se/~cschulte/paper.php?id=SchulteStuckey:PPDP:2008

 

I hope that helps.

 

Best

Christian

 

--

Christian Schulte, Professor of Computer Science, KTH,
www.ict.kth.se/~cschulte/

 

From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Zhu Zichen's cse
Sent: Tuesday, September 03, 2013 4:38 AM
To: users at gecode.org
Subject: [gecode-users] Expr() in GECODE

 

Hi,

 

I have a question.

For GECODE,

When I use expressions:

     BoolVar sofar = expr( home,( !_A[i]   ||   x[index] != val ));// where
_A[i] is a BoolVar, and x is IntVarArray, index and val are integer. 

 

If I rewrite it as:

     if(_A[i].one())

      sofar = expr( home, x[index] != val);

     else

      sofar = expr( home,( !_A[i]   ||   x[index] != val));

There will be a great improvement on runtime, say 40%.

 

If I rewrite it as:

   if(_A[i].one())

     x[index].nq(val);

   else

    sofar = expr( home,( !_A[i]   ||   x[index] != val));

There will be another improvement on the latest one for runtime, say 30%.

 

 

For ILOG,

 IlcConstraint sofar =   (! _A[i]) ||     x[index] != val ) ;

 

Rewrite as:

     if(_A[i].isTrue()==IlcTrue) 

        sofar = x[index] != val;

    else

       sofar =   (! _A[i]) ||     x[index] != val ) ;

Running times of the above two methods are the same.

 

 

 

Is this because the "inefficient" of expr() to handle  Boolean expressions
and relations in GECODE?

 

 

Thanks!

 

Zichen

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20130903/bb5606dc/attachment.html>