<: "until goal"

[Kilian Sprotte]

Dear Raphael,

thank you so much! Your solution is exactly what I needed!!
This "propagator" is very useful for computing segmentations of a given
length N (e.g. 5):

5
4 1
3 2
3 1 1
2 3
2 2 1
2 1 2
2 1 1 1
1 4
1 3 1
1 2 2
1 2 1 1
1 1 3
1 1 2 1
1 1 1 2
1 1 1 1 1

The real model in Oz would be:

5 0 0 0 0
4 1 0 0 0
3 2 0 0 0
3 1 1 0 0
2 3 0 0 0
2 2 1 0 0
2 1 2 0 0
2 1 1 1 0
1 4 0 0 0
1 3 1 0 0
1 2 2 0 0
1 2 1 1 0
1 1 3 0 0
1 1 2 1 0
1 1 1 2 0
1 1 1 1 1

When I have another sequence of same length that represents the  
"partial sums" from left until each point, I need your propagator to  
make it increasing until the goal is reached and thus allowing  
zeroes, but only at the end (this is related to a problem of Torsten  
Anders).

Just imposing {FD.sum MySequence '=:' 5} as I did in the beginning,  
does not propagate very well as soon as the domains contain zeroes.

Now, your propagator allows me to get /maximum propagation/ [1] !!! :)

Many thanks again,
   Kilian

[1] About maximum propagation: I just discovered for myself this  
probably very well known concept....what I enjoy about it that it is  
perfectly possible to define it (empirically) by analyzing an all  
solution search... By comparing this with a propagator to be tested  
you can see exactly what you are missing and your help leads me to  
100% propagation !

I am wondering whether you pros are using this kind of strategy of  
unit testing when developing new propagators?

Am 04.04.2007 um 09:28 schrieb Raphael Collet:

> Dear Kilian,
>
> I scratched my head quite a bit yesterday, and I just found a nice  
> solution to your problem.  The idea is to avoid reification,  
> because propagation is too poor in that case.
>
> Kilian Sprotte wrote:
>> I am looking for a way to constrain a sequence to be "ascending  
>> towards a goal". The goal is determined before posting, let's say  
>> its 5, so a solution could be:
>> [1 2 4 5 5]
>
> Let us call this sequence S.  It can be defined as:
>
> 	declare
> 	Goal=5
> 	N=5
> 	S={FD.list N 1#Goal}
>
> The issue is that S is strictly increasing, except when values  
> reach the goal.  My idea is to combine the propagators <: and  
> FD.min.  Consider another sequence, say T, that is strictly  
> increasing, and where values may be greater than the goal:
>
> 	declare
> 	T={FD.list N 1#(Goal+N-1)}
> 	for A in T  B in T.2 do A <: B end   % strictly increasing
>
> The link with S is done by taking the minimum between the Goal and  
> each element of T:
>
> 	for X in S  Y in T do X={FD.min Goal Y} end
>
> Both propagators <: and FD.min will propagate of the variables'  
> domains, and propagates exactly as you wanted:
>
>>  [1#5 2#5 3#5 4#5 5]
>
> Try to constrain the 3rd element of S to value 4 in the example,  
> and you will see that the 4th element is constrained to 5.
>
>
> Cheers,
> raph
> ______________________________________________________________________ 
> ___________
> mozart-users mailing list                               mozart- 
> users at mozart-oz.org
> http://www.mozart-oz.org/mailman/listinfo/mozart-users