1

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).

Ryan Goodfellow
  • 13
  • 3

3 Answers3

1

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.

Olivier Lhomme
  • 91
  • 1
  • Thanks for this, and for the replies from everyone else. I ended up solving this last night but didn't get a chance to check the responses. This was closest to my implementation, so it was selected. I truly appreciate everyone's time helping me understand different approaches. – Ryan Goodfellow Feb 03 '23 at 18:14
0

In scheduling, the concept of a cumulative constraint is usually reserved for resources that have a maximum usage at each time index, as you talk about in the final sentence.

What you are talking about seems to be more of a sliding sum constraint, which limits the sum of variables in any contiguous subsequence of a certain length.

Zayenz
  • 1,914
  • 12
  • 11
0

If you want to reason about the daily contributions, you can model each task as a chain of consecutive intervals, each a single day long, and each contributing at the begin/end of the day. E.g. using the Python API:

from docplex.cp.model import CpoModel

m = CpoModel()

cumul_contribs = []

# Task A
task_a = m.interval_var_list(6, start=(0,100),end=(0,100), size=1, name='a')
for (ivl1,ivl2) in zip(task_a, task_a[1:]):
    m.add(m.end_at_start(ivl1, ivl2))
for ivl in task_a:
    cumul_contribs.append(m.step_at_start(ivl, 5))

# Task B
task_b = m.interval_var_list(3, start=(0,100),end=(0,100), size=1, name='b')
for (ivl1,ivl2) in zip(task_b, task_b[1:]):
    m.add(m.end_at_start(ivl1, ivl2))
for ivl in task_b:
    cumul_contribs.append(m.step_at_start(ivl, 10))

# Constrain the cumulative resource
m.add(m.always_in(sum(cumul_contribs), (0,5), 0, 50))

msol = m.solve()
msol.write()
jschimpf
  • 4,904
  • 11
  • 24