[gecode-users] cumulatives constraint

[Mikael Zayenz Lagerkvist]

Hi,

On Tue, Apr 15, 2008 at 12:09 PM, David Rijsman <davidrijsman at gmail.com> wrote:
<snip/>
>  I would expect the start of the second variable to be pruned from
>  [0,40] to [20,40] but what we see (when we run the attached file) is a
>  search on the start variable failing 20 times (trying start
>  0,1,2,...19) before finding the first solution. Obviously I expect the
>  first decision to be a solution. Am I expecting to much propagation on
>  a task without compulsory part?

You are quite right in that there should be more pruning. I've looked
into the code, and unfortunately there was a bug that made the pruning
much weaker than it should have been (it never did anything wrong,
just not enough).

I've fixed the bugs I found in the trunk-version, and your example now
has no failures. Thank you very much for the bug-report. If you don't
want to use the trunk-version, send me an e-mail, and I'll send a diff
of the relevant file to you.

If you are planning to use cumulatives as a standard cumulative, you
should know that there are other algorithms for cumulative that might
give more pruning. In particular, edge-finding and not-first/not-last
are commonly used. These are unfortunately not available in Gecode
currently.

Cheers,
Mikael

-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/