[gecode-users] Propagating to Fixpoint

Guido Tack tack at gecode.org
Thu Aug 23 16:16:37 CEST 2012 

I'm not sure, I just think there could be cases where (especially if you use MiniModel) the posting function does some additional reasoning.

Cheers,
Guido

-- 
Guido Tack
http://www.csse.monash.edu/~guidot/



On 23/08/2012, at 2:04 PM, Max Ostrowski <ostrowsk at cs.uni-potsdam.de> wrote:

> Great, this really solves the problem.
> Have not thought of this.
> Thank you very very much.
> In my example everything works as expected and the fixpoint is always the same.
> Are you sure that it can still happen that the fixpoint of the same set of constraints is different,
> if i use a different order?
> Then i have to stick to my fallback method.
> 
> 
> Nevertheless,
> big thanks for solving my problem. Everything works now and is a hundred times faster :)
> 
> Best,
> Max
> 
> On 08/23/2012 01:44 PM, Guido Tack wrote:
>> 
>> Without looking at the details: Do you check the return value of IntView::lq?  The view functions are not meant to be used in models. If lq returns failure, you have to check that yourself, or the space won't be failed.
>> 
>> Cheers,
>> Guido
>> 
>> -- 
>> Guido Tack
>> 
>> 
>> On 23/08/2012, at 13:20, Max Ostrowski <ostrowsk at cs.uni-potsdam.de> wrote:
>> 
>>> Actually its quite complicated.
>>> I'm currently debugging and have 60 constraints written on paper that have this effect.
>>> Two of them are actually not reified constraints but directly using IntView::lq(constant)
>>> 
>>> I can give you a description where it happens in my system, but it will be a mess for you to write simplified code that reproduces this.
>>> 
>>> Actually given two spaces original1 and original2 that are equal,
>>> variables are constraint like this:
>>> posx(6)=[0..185] posx(5)=[0..190] posx(4)=[0..142] posx(3)=[0..158] posx(2)=[0..113] posx(1)=[0..157]
>>> 
>>> all reified constraints are posted with free boolean variables, using
>>> 
>>> 
>>> linear(*this, intArgs, intVarArgs, r,0,b_[boolvar],ICL_DEF);
>>> 
>>> Now i set the boolean variables accordingly, always doing propagation (calling status()) after each single posting
>>> 
>>> To original1 false ((-1 $* posx(3))+posx(1))$<=0
>>> To original1 false ( 10+(-1 $* posx(6))+posx(5))$>0
>>> To original1 false ( 58+(-1 $* posx(5))+posx(4))$>0
>>> To original1 true posx(6)<=69                            // this is no reified constraint, but just posted IntView(posx(6)).lq(69)
>>> To original1 false ( 43+(-1 $* posx(6))+posx(1))$>0
>>> To original1 false ((-1 $* posx(5))+posx(2))$<=0
>>> To original1 true ((-1 $* posx(1))+posx(3))$<=0
>>> To original1 true ((-1 $* posx(4))+posx(3))$<=0
>>> To original1 false ( 42+(-1 $* posx(5))+posx(3))$>0
>>> To original1 false ( 42+(-1 $* posx(6))+posx(3))$>0
>>> To original1 true ( -42+(-1 $* posx(3))+posx(1))$<0
>>> To original1 true ( -15+(-1 $* posx(6))+posx(1))$<0
>>> To original1 true ( 58+(-1 $* posx(1))+posx(4))$>0
>>> To original1 true ( 42+(-1 $* posx(1))+posx(3))$>0
>>> To original1 false ((-1 $* posx(1))+posx(2))$<=0
>>> To original1 true ((-1 $* posx(6))+posx(1))$<=0
>>> To original1 true ((-1 $* posx(5))+posx(1))$<=0
>>> To original1 true ( -10+(-1 $* posx(5))+posx(1))$<0
>>> To original1 true ((-1 $* posx(2))+posx(1))$<=0
>>> To original1 false ( 43+(-1 $* posx(2))+posx(1))$>0
>>> To original1 true ( -28+(-1 $* posx(1))+posx(6))$>0
>>> To original1 false ( 28+(-1 $* posx(6))+posx(1))$>0
>>> To original1 false ( -43+(-1 $* posx(1))+posx(2))$<0
>>> To original1 true ( -58+(-1 $* posx(4))+posx(1))$<0
>>> To original1 true posx(1)<=29                          // this is no reified constraint, but just posted IntView(posx(1)).lq(29)
>>> To original1 false ((-1 $* posx(1))+posx(4))$<=0       // lets call this constraint X
>>> 
>>> Now this space is failed.
>>> 
>>> Something similar with the second space, but posting nr. 5 is different.
>>> 
>>> To original2 false ((-1 $* posx(3))+posx(1))$<=0
>>> To original2 false ( 10+(-1 $* posx(6))+posx(5))$>0
>>> To original2 false ( 58+(-1 $* posx(5))+posx(4))$>0
>>> To original2 false ((-1 $* posx(1))+posx(4))$<=0       // this is constraint X, it is now posted on this position, no longer as the last constraint anymore
>>> To original2 true posx(6)<=69                          // this is no reified constraint, but just posted IntView(posx(6)).lq(69)
>>> To original2 false ( 43+(-1 $* posx(6))+posx(1))$>0
>>> To original2 false ((-1 $* posx(5))+posx(2))$<=0
>>> To original2 true ((-1 $* posx(1))+posx(3))$<=0
>>> To original2 true ((-1 $* posx(4))+posx(3))$<=0
>>> To original2 false ( 42+(-1 $* posx(5))+posx(3))$>0
>>> To original2 false ( 42+(-1 $* posx(6))+posx(3))$>0
>>> To original2 true ( -42+(-1 $* posx(3))+posx(1))$<0
>>> To original2 true ( -15+(-1 $* posx(6))+posx(1))$<0
>>> To original2 true ( 58+(-1 $* posx(1))+posx(4))$>0
>>> To original2 true ( 42+(-1 $* posx(1))+posx(3))$>0
>>> To original2 false ((-1 $* posx(1))+posx(2))$<=0
>>> To original2 true ((-1 $* posx(6))+posx(1))$<=0
>>> To original2 true ((-1 $* posx(5))+posx(1))$<=0
>>> To original2 true ( -10+(-1 $* posx(5))+posx(1))$<0
>>> To original2 true ((-1 $* posx(2))+posx(1))$<=0
>>> To original2 false ( 43+(-1 $* posx(2))+posx(1))$>0
>>> To original2 true ( -28+(-1 $* posx(1))+posx(6))$>0
>>> To original2 false ( 28+(-1 $* posx(6))+posx(1))$>0
>>> To original2 false ( -43+(-1 $* posx(1))+posx(2))$<0
>>> To original2 true ( -58+(-1 $* posx(4))+posx(1))$<0
>>> To original2 true posx(1)<=29                                        // this is no reified constraint, but just posted IntView(posx(1)).lq(29)
>>> 
>>> This Space is not failed
>>> 
>>> 
>>> 
>>> 
>>> I know this is quite a huge blob of data and you probably wont have the time to reconstruct it.
>>> I will just have to adjust my code that this can happen.
>>> BTW: Can you confirm that this is due to the use of IntView::lq ?
>>> I never experienced this without them.
>>> 
>>> Best,
>>> Max
>>> 
>>> 
>>> 
>>> 
>>> On 08/23/2012 12:40 PM, Guido Tack wrote:
>>>> 
>>>> I guess under certain conditions the code that posts the constraints (not the actual propagator) can be stronger than ICL_DEF, in which case this can happen.
>>>> If it's not too complicated, could you send us a concrete example?
>>>> 
>>>> Cheers,
>>>> Guido
>>>> 
>>>>   
>>> 
>>> _______________________________________________
>>> 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20120823/6be381d2/attachment-0001.html>

More information about the users mailing list