[gecode-users] Remapping of BoolVar propagation conditions

[Vincent Barichard]

Hi,

I knew that the flag thing would not be possible. I will follow your  
advice and
investigate further the BoolView changes.

I know that it must be very difficult for you to help me without  
really know what I am trying to do.
For now I launch benchmarks and try to write something about it. If  
you are interested in and have
free time, I will send you the paper.

Thank you very much to you and Guido for all your answer. They are all  
very useful to me.

Cheers,
Vincent

Le 4 déc. 09 à 16:02, Christian Schulte a écrit :

> Hi,
>
> Sorry, but the flag thing will not work. You would have to rewrite the
> entire kernel and how the variable stubs are automatically generated  
> to pull
> that off.
>
> I think we discussed already that you have to move out the rewriting  
> from
> the varimp to the views.
>
> As it comes to what is most effort I can't really say as I don't  
> know what
> you want to do. If I just wanted to clarify whether a propagator  
> uses a
> Boolean variable as a Boolean variable or an integer variable I'd do  
> what I
> said.
>
> Cheers
> Christian
>
> --
> Christian Schulte, www.ict.kth.se/~cschulte/
>
> -----Original Message-----
> From: Vincent Barichard [mailto:Vincent.Barichard at univ-angers.fr]
> Sent: Wednesday, December 02, 2009 10:38 PM
> To: Christian Schulte
> Cc: 'Guido Tack'; 'gecode list'
> Subject: Re: [gecode-users] Remapping of BoolVar propagation  
> conditions
>
> Hi Christian,
>
> As the remapping is done in VarImp and not in View, I don't see how to
> solve my problem by defining another View.
> For example, if I want to make element constraint over booleans
> variables subscribe to PC_BOOL_SAME, I update the constructor of
> "Int<V0,V1,Idx,Val>" to make views x0 and x1 subscribe to PC_INT_DOM
> and PC_BOOL_SAME. If I use the new view, boolean variable will
> subscribe to PC_INT_DOM instead to PC_BOOL_VAL and integer variables
> will subscribe to PC_BOOL_SAME that is not meaningful for them.
>
> Maybe if subscribe functions could be called like that :
> x0.subscribe(home, *this, PC_INT_DOM | PC_BOOL_VAL);
> with PC_X_X propagation conditions seen as flag, the subscribe
> function of a view may be able to deal only with
> conditions meaningful for the view and ignore others. For example, in
> x0.subscribe(home, *this, PC_INT_DOM | PC_BOOL_VAL | PC_BOOL_SAME),
> PC_INT_DOM is only meaningful for IntView and PC_BOOL_VAL and
> PC_BOOL_SAME are only meaningful for BoolView. Other problems will
> occur like the maximum number of PC_X_X conditions managed in Gecode.
> Sorry my guess is probably irrelevant, but I don't see how to do
> without changing even a
> little the propagators.
>
> Furthermore, all current "rel()" functions which post propagators use
> usual BoolView.So I have to change all functions which post
> propagators to make them post propagators with the new view. I think
> that It is more painful than just updating the constructor of some
> propagators.
>
> Sorry to bother you with my questions. I think Gecode is a great
> solver and I like to add inside it
> my ideas in order to validate them..
>
> Cheers,
> Vincent
>
> Le 2 déc. 09 à 19:06, Christian Schulte a écrit :
>
>> No, that wouldn't really work as I think it is best to not change
>> the code
>> of the propagators: that's the entire idea behind views!
>>
>> I would be happier if your first sentence would read as follows: ...
>> the
>> remapping is only meaningful for propagators which use boolean
>> variables as
>> (instead of and) integer variables.
>>
>> So, what's so bad about defining two views and instantiate the
>> propagators
>> accordingly? I even thought that this should have been done in
>> Gecode right
>> from the start.
>>
>> Christian
>>
>> -----Original Message-----
>> From: Vincent Barichard [mailto:Vincent.Barichard at univ-angers.fr]
>> Sent: Wednesday, December 02, 2009 2:45 PM
>> To: Christian Schulte
>> Cc: 'Guido Tack'; 'gecode list'
>> Subject: Re: [gecode-users] Remapping of BoolVar propagation
>> conditions
>>
>> Hi,
>>
>> Ok, if I understood all answers, the remapping is only meaningful for
>> propagators which use boolean variables and integer variables. As  
>> they
>> can't distinguish boolean variables from integer ones, the  
>> propagation
>> conditions are remapped in the first case.
>>
>> If the propagators might distinguish boolean variables from integer
>> variables, and use the correct propagation condition in each case,  
>> the
>> remapped will be useless.
>>
>> If I modify the ViewVarImpTraits and the constructors of propagators
>> in the following way, will all existing propagators of Gecode work as
>> usual ? In that case I will be able to add a new PC_BOOL_SAME
>> condition without breaking anything.
>>
>> In gecode/int/view.hpp, I change all ViewVarImpTraits classes:
>>
>> Those which are over booleans,
>>
>>  template<>
>>  class ViewVarImpTraits<Int::IntView> {
>>  public:
>>    /// The variable type of an IntView
>>    typedef Int::IntVarImp VarImp;
>>    static const bool isBool = false;
>>  };
>>
>> Those which deal with booleans,
>>
>>  template<>
>>  class ViewVarImpTraits<Int::BoolView> {
>>  public:
>>    /// The variable type of a BoolView
>>    typedef Int::BoolVarImp VarImp;
>>    static const bool isBool = true;
>>  };
>>
>>
>> and in propagator constructors (for example in gecode/int/element/
>> int.hpp) replace calls to :
>>
>> x0.subscribe(home,*this,PC_INT_DOM);
>>
>> by
>>
>> x0.subscribe(home,*this,(Gecode::ViewVarImpTraits<V0>::isBool)?
>> PC_BOOL_VAL:PC_INT_DOM);
>>
>> After, in the file gecode/int/var-imp/bool.hpp :
>>
>>  forceinline void
>>  BoolVarImp::subscribe(Space& home, Propagator& p, PropCond,
>>                        bool process) {
>>    // Subscription can be used with integer propagation conditions,
>>    // which must be remapped to the single Boolean propagation
>> condition.
>>    BoolVarImpBase::subscribe(home,p,PC_BOOL_VAL,assigned(),process);
>>  }
>>
>> can be replaced by
>>
>>  forceinline void
>>  BoolVarImp::subscribe(Space& home, Propagator& p, PropCond pc,
>>                        bool process) {
>>    BoolVarImpBase::subscribe(home,p,pc,assigned(),process);
>>  }
>>
>> (the same for the cancel member function)
>>
>> and everything should work as usual.
>> Am I right ?
>>
>> Cheers,
>> Vincent
>>
>>
>> Le 1 déc. 09 à 19:26, Christian Schulte a écrit :
>>
>>> Actually, what Guido and me tried to say is the following:
>>> conceptually,
>>> Gecode should have two Boolean views, say BoolView and
>>> BoolAsAnIntView. The
>>> former does not need rewriting and most propagators using Boolean
>>> views
>>> should use this one. The latter must use rewriting to map integer
>>> propagation conditions to the single supported Boolean propagation
>>> condition.
>>>
>>> Then there are integer propagators which we also want to use on
>>> Boolean
>>> views (these are few: the extensional ones, including element and
>>> sequence).
>>> These propagators should use BoolAsAnIntView including rewriting.
>>> All other
>>> - true Boolean propagators should use the real BoolView.
>>>
>>> So what you might want to do is to have these two different views,
>>> one with
>>> and one without rewriting! Everything will work just fine.
>>>
>>> Christian
>>>
>>> -----Original Message-----
>>> From: Vincent Barichard [mailto:Vincent.Barichard at univ-angers.fr]
>>> Sent: Tuesday, December 01, 2009 6:22 PM
>>> To: Guido Tack
>>> Cc: Christian Schulte; 'gecode list'
>>> Subject: Re: [gecode-users] Remapping of BoolVar propagation
>>> conditions
>>>
>>> Hi Guido,
>>>
>>> That was my first thought. But I didn't understand why this  
>>> remapping
>>> was there. Christian said in a previous mail that removing the
>>> mapping
>>> will break all propagators that are used for integer as well as for
>>> boolean variables! If I pass the pc unchanged, will it break
>>> something
>>> in Gecode ? I don't want to break something, I would like to add
>>> safely my piece of code.
>>>
>>> If removing it doesn't break anything, will this mapping be still
>>> there in the future versions ?
>>>
>>> Thank you again, I really appreciate the time you spent to answer my
>>> questions :)
>>>
>>> Cheers,
>>> Vincent
>>>
>>> Le 1 déc. 09 à 16:30, Guido Tack a écrit :
>>>
>>>> Hi Vincent,
>>>>
>>>> the rewriting is currently done in int/var-imp/bool.hpp.  Just
>>>> remove the rewriting there and pass the pc unchanged, add rewriting
>>>> to all the normal Gecode BoolView classes, and then add your own
>>>> BoolView class that doesn't rewrite.
>>>>
>>>> Cheers,
>>>>    Guido
>>>>
>>>> Vincent Barichard wrote:
>>>>
>>>>> Dear Christian,
>>>>>
>>>>> Thank you very much for your mail. I'm sorry, I don't understand
>>>>> your answer. Why having other BoolView classes will
>>>>> help me ? I added member functions in the BoolViews classes. I
>>>>> didn't change the existing ones,
>>>>> I only added member functions which notify the ME_BOOL_SAME event.
>>>>>
>>>>> In my own propagator (let's call it M) I call the recently added
>>>>> functions in the BoolViews. So the ME_BOOL_SAME
>>>>> event is sent.
>>>>>
>>>>> I also modified one propagator of Gecode (let's call it P') and
>>>>> make it subscribe to the PC_BOOL_SAME propagation condition (I  
>>>>> only
>>>>> added "x1.subscribe(home, *this, PC_BOOL_SAME)" in constructor).
>>>>> In the "propagate" function of P' I added instructions which are
>>>>> only relevant if a ME_BOOL_SAME event has been sent before.
>>>>>
>>>>> So when M is woke up (because it subscribe to PC_BOOL_VAL
>>>>> propagation condition) it may call the new member functions in the
>>>>> BoolViews classes which sent the ME_BOOL_SAME event. I would like
>>>>> that propagators which subscribe to the PC_BOOL_SAME propagation
>>>>> condition and only these ones, be scheduled to wake up (for  
>>>>> example
>>>>> P' will be scheduled if it shares a variable with M). As no
>>>>> assignment has been made by the M propagator, I don't want that
>>>>> other propagators wake up except if a ME_BOOL_VAL event has been
>>>>> sent from elsewhere.
>>>>>
>>>>> Unfortunately, as all propagation condition subscribings for
>>>>> Boleans variables are remapped to PC_BOOL_VAL, P' will not awake  
>>>>> if
>>>>> a ME_BOOL_SAME event is sent.
>>>>>
>>>>> May have I another choice but to use the ME_BOOL_VAL event instead
>>>>> of ME_BOOL_SAME in my new member functions of the BoolView
>>>>> classes ? As a result, all propagators will be awaken even if they
>>>>> can't propagate removal, indeed no assignment has been made.
>>>>>
>>>>> Don't hesitate to ask me if I'm not clear enough.
>>>>>
>>>>> Cheers,
>>>>> Vincent
>>>>>
>>>>> Le 30 nov. 09 à 16:35, Christian Schulte a écrit :
>>>>>
>>>>>> Actually what you have to do is the following: you define two
>>>>>> classes for
>>>>>> Boolean views, one that rewrites its propagation conditions and
>>>>>> the other
>>>>>> one that does not. Then your propagators can use the views  
>>>>>> without
>>>>>> rewriting
>>>>>> while the other propagators can use the variables with rewriting.
>>>>>>
>>>>>> Christian
>>>>>>
>>>>>> --
>>>>>> Christian Schulte, www.ict.kth.se/~cschulte/
>>>>>>
>>>>>>
>>>>>> -----Original Message-----
>>>>>> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org]
>>>>>> On Behalf
>>>>>> Of Vincent Barichard
>>>>>> Sent: Monday, November 30, 2009 9:33 AM
>>>>>> To: Christian Schulte
>>>>>> Cc: 'Guido Tack'; 'gecode list'
>>>>>> Subject: Re: [gecode-users] Remapping of BoolVar propagation
>>>>>> conditions
>>>>>>
>>>>>> Hi,
>>>>>>
>>>>>> Thank you both for your answers. As I don't want to break all
>>>>>> propagators
>>>>>> that are used for integer as well as boolean variables, I see no
>>>>>> choice but
>>>>>> to use PC_BOOL_VAL.
>>>>>>
>>>>>> Maybe one of you may see another way ? I make new functions on
>>>>>> Boolean
>>>>>> variables (and associated views) which don't set domain to 1 or 0
>>>>>> (I copied
>>>>>> "ModEvent  BoolVarImp::one_none(Space& home)" and removed the
>>>>>> unwanted
>>>>>> instructions). These functions notify new events (called
>>>>>> ME_BOOL_SAME in
>>>>>> bool.vis file (see attached file)). I mapped this new event to  
>>>>>> the
>>>>>> PC_BOOL_SAME propagation condition.
>>>>>>
>>>>>> Now I change an existing propagator (like the "Or" propagator),
>>>>>> and I want
>>>>>> it to be awaken when ME_BOOL_SAME is emitted. As the variable is
>>>>>> not yet
>>>>>> assigned, I didn't want to emit the ME_BOOL_VAL event because I
>>>>>> didn't want
>>>>>> to wake up propagators which only subscribed to the PC_BOOL_VAL
>>>>>> condition.
>>>>>>
>>>>>> So during propagation, I call my new functions on Boolean
>>>>>> variables, the
>>>>>> ME_BOOL_SAME event is sent and propagators which subscribe to the
>>>>>> PC_BOOL_SAME condition are wake up. Other propagators are not
>>>>>> awaken (except
>>>>>> if a ME_BOOL_VAL event has also been sent). Is it possible ?
>>>>>> Should I use ME_BOOL_VAL ? If I use ME_BOOL_VAL other propagators
>>>>>> will be
>>>>>> awaken for nothing.
>>>>>>
>>>>>> Thanks for your help.
>>>>>>
>>>>>> Cheers,
>>>>>> Vincent
>>>>>
>>>>> Vincent Barichard         Université d'Angers (LERIA)
>>>>> Tel: 02 41 73 52 06      Département Informatique
>>>>> Fax: 02 41 73 50 73     H203
>>>>>
>>>
>>> Vincent Barichard         Université d'Angers (LERIA)
>>> Tel: 02 41 73 52 06      Département Informatique
>>> Fax: 02 41 73 50 73     H203
>>>
>>
>> Vincent Barichard         Université d'Angers (LERIA)
>> Tel: 02 41 73 52 06      Département Informatique
>> Fax: 02 41 73 50 73     H203
>>
>
> Vincent Barichard         Université d'Angers (LERIA)
> Tel: 02 41 73 52 06      Département Informatique
> Fax: 02 41 73 50 73     H203
>

Vincent Barichard         Université d'Angers (LERIA)
Tel: 02 41 73 52 06      Département Informatique
Fax: 02 41 73 50 73     H203