finite set select intersection (Raphael Collet)

[Raphael Collet]

Hi Irene,

Let me first congratulate you on the birth of your son!


You wrote:
> 
> Thanks Raph for the helpful suggestion.  Your version is cleaner and
> more complete, although for my particular problem I can't rule out
> empty sets, which weakens the propagation.   I tried a sample run, and
> didn't notice any change in search tree size or significant difference
> in run time, which seems a little surprising.

That's why I wrote about a "slightly" improved definition ;-)

The problem with empty sets is that they potentially introduce
symmetries in the problem.  Unless they are rare in your problem, you
should try to treat them separately.  That will improve propagation if
you have specific constraints on which empty sets must be selected.

One possibility is to let the partition propagator rule them out (my
implementation does), and have a separate propagator for them.  Here is
for instance a propagator that selects the empty sets among Sets.  You
can then decide which subset of SelectorSet must be joined with the
partition.

proc {SelectEmpty Sets SelectorSet}
   Selector
in
   %% Selector reifies the presence of each set
   SelectorSet={FS.var.upperBound 1#{Length Sets}}
   Selector={FS.reified.areIn 1#{Length Sets} SelectorSet}
   
   %% I is in SelectorSet iff {Nth Sets I} is empty
   for S in Sets  Sel in Selector do
      Sel = ({FS.card S} =: 0)
   end
end

In case you want SelectPartition to select all empty sets, simply
replace

   %% selected sets must be non-empty
   for S in Sets  Sel in Selector do Sel =<: {FS.card S} end

by

   %% empty sets are selected
   for S in Sets  Sel in Selector do Sel + {FS.card S} >: 0 end


Cheers,

raph