[gecode-users] Partial sums

[Christian Schulte]

Hmm, maybe there is a compromise between the two encodings for partial sums.

Let me just sketch the idea: break up in a tree shaped fashion rather than
either in a chain or diagonal fashion. So as an example, consider the
partial sums:
 s_0 = x_0
 s_1 = x_0 + x_1
 s_2 = x_0 + x_2 + x_3
 s_3 = x_0 + x_2 + x_3 + x_4

Then you could rewrite to
 s_0 = x_0
 s_1 = x_0 + x_1
 s_2 = s_1 + x_2
 s_3 = s_1 + x_2 + x_3

That would prevent the disadvantages of the chain encoding (propagation
between x_0 and x_{n-1} taking n steps) and the diagonal encoding of O(n)
propagators with O(n^2) variables. It should give O(log n) steps between x_0
and x_n and O(n log n) variables in all propagators when generalized to
arbitrary n.

Cheers
Christian 

--
Christian Schulte, www.ict.kth.se/~cschulte/ 


-----Original Message-----
From: Malcolm Ryan [mailto:malcolmr at cse.unsw.edu.au] 
Sent: Thursday, November 29, 2007 12:21 AM
To: cschulte at kth.se
Subject: Re: [gecode-users] Partial sums


On 29/11/2007, at 2:16 AM, Christian Schulte wrote:

> Hi Malcolm,
>
> Nice question! First, after some thinking I would say that both  
> provide the
> same strength of propagation for both bounds and domain consistency  
> (that is
> not obvious, actually). If the terms in the sum had non-unary  
> coefficients
> propagation would be different, with the ternary constraints having  
> weaker
> propagation.
>
> Then, the number of propagation steps required for version (1)  
> should be
> lower than those for (2). However, the propagators for (1) are more  
> costly.
>
> So, I would just try it out, trying (2) first. How many variables  
> are we
> talking by the way? Tens? Hundreds? Thousands?

Well, it depends on the scale of the problem, but probably tens or  
hundreds, not thousands.

Malcolm

--
      "The Christian ideal has not been tried and found wanting;
       it has been found difficult and left untried."
             - G.K.Chesterton, What's Wrong With The World