[SOLVED] Constraint Programming CP Optimizer - How to model a cumulative capacity constraint

Constraint Programming CP Optimizer - How to model a cumulative capacity constraint

I am new to the CP Optimizer (from ILOG), and am trying to find the right keywords to get me on a track to modelling cumulative capacity constraints.

For example, I have two tasks:

A, which lasts for 6 days and contributes 5 units per day to a cumulative capacity constraint

B, which lasts for 3 days and contributes 10 units per day to a cumulative capacity constraint

I would like to put in a cumulative capacity constraint over an interval. For example, a constraint from days 0,...,4 with a maximum cumulative value of 50.

Scheduling A and B to both start at day 0 would yield a cumulative contribution of:

A: 5 + 5 + 5 + 5 + 5 = 25 (with the remaining 5 outside of this interval not hitting this constraint)

B: 10 + 10 + 10 = 30

This would exceed the cumulative capacity of 50 over that timespan. However, if I move the intervals such that A starts on day 1 (rather than 0) and B starts on day 0, then

A: 5 + 5 + 5 + 5 = 20 (with the remaining 5+5 outside of this interval not hitting this constraint)

B: 10 + 10 + 10 = 30

This schedule would satisfy this constraint.

Can someone please help me find the right functions / words to solve this? I realize this could be trivial for experts in CP. I don't necessarily need full code, just pointing me in the right direction would be extremely helpful!

I have tried to use StepAtEnd for A and B, however, this lets task A completely slide under the capacity of 50 units. StepAtStart will push A or B outside of the constraint window. I understand that an alternative approach would be to put a constraint on 10 units per day, but I am intentionally trying to model this as a cumulative constraint (in the bigger picture, letting daily constraints flex above 10, but ultimately staying under 50 cumulatively over a specific window).

Solution

For computing the integral of a cumul function over the period T, you can do as follows.

Let f be the cumul function (in your case pulse(A,6) + pulse(B,10)).

Let the period T = [t0, t0+k).

Let z_i be a fixed interval of size 1, starting at t0+i, for i in 0..k-1. (the z_i's cover T)

Let g be a new cumul function

defined by: g=sum(pulse(z_i, 0, MAX))
and constrained by: g+f==MAX.

Then, F, the integral of f over the period T is: F = T*MAX - Sum(heightAtStart(z_i, g))

And for your problem, you just need to constrain F to be less than or equal to 50.