[gecode-users] Remapping of BoolVar propagation conditions
Vincent Barichard
Vincent.Barichard at univ-angers.fr
Wed Dec 2 22:38:10 CET 2009
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
More information about the users
mailing list