Cumulative constraint with lower bounds

[Dr-Irv]

We are working on a scheduling problem with the following characteristics.

We have a lot of optional interval variables representing subtasks on tasks, each has lower and upper bounds on their start/end times, and a lower bound on duration if active. Each interval variable (a subtask) is indexed by a task and a device. The intervals do not cover the entire planning horizon. E.g., if you are doing 2 years of scheduling, with time units of days, each interval might be no longer than 10 days at most (due to the data), and in the 2 year time frame, there may only be 10 or 20 intervals available, so there will be a lot of holes in the schedule (which is fine).

For each task, you have to assign as many subtasks (across devices) as you can, but exactly N (2, 3, or more - depends on the data) devices must be active any time you do an assignment.

Each device can only do at most one task at a time.

I don't see how to model the first constraint with CP-SAT. The second one is straightforward - the add_cumulative() constraint will work.

With CPLEX CP Solver, there is a cumul_range() constraint that lets you specify both the lower and upper bounds for the active intervals at any one time. But with CP-SAT, you can only specify the upper bound, and not the lower bound. We would need to specify the value N as a lower and upper bound so that exactly N subtasks were active at any time that the subtasks for the parent task were active.

What is the right way to model this with CP-SAT?

[lperron]

Let's assume all intervals are performed.

If you have the complementary intervals (0..start) and (end..horizon) and add them to a cumulative with capacity sum of demands.

Forcing a min of k on during [a..b] is equivalent to adding a fixed interval with a demand k on [a..b], or in other words, changing the max profile of the cumulative.

You can also use reservoirs.

[Dr-Irv]

Let's assume all intervals are performed.

But we can't do that. They are all optional.

If you have the complementary intervals (0..start) and (end..horizon) and add them to a cumulative with capacity sum of demands.

Sum of which demands?

Forcing a min of k on during [a..b] is equivalent to adding a fixed interval with a demand k on [a..b], or in other words, changing the max profile of the cumulative.

I don't understand this comment.

You can also use reservoirs.

I don't see how to do that because the lower bound of a reservoir has to be nonpositive. If the lower bounds could be positive, then we'd be all set.

Fundamentally, we need to make sure that when the "real" intervals are present, there are exactly K of them present at any time. I see how the complementary intervals will fill in the holes, but I don't see how you force K Of them to be active at each time.

[lperron]

Let's take a simple example.

2 intervals [s1..e1] , [s2..e2] with demand 2 and 3 and presence literals p1 and p2.

create an additional cumulative with 4 intervals

[0..s1] and [e1..horizon], both with presence literals p1 and demand 2
[0..s2] and [e2..horizon], both with presence literals p2 and demand 3

cumulative has capacity p1 * 2 + p2 * 3.

Now, you want min usage to be 2 during [3..5]

add a 5th demand with a fixed performed interval [3..5] and a demand of 2.

This implements your request.

[Dr-Irv]

I still don't see how to apply your solution in our case, because we don't want the min usage to be a minimum during a fixed interval. We want the min usage to be true whenever the intervals are present.

Let's say we have N intervals.
Each interval has a range of start and end times, [start1, end1], [start2, end2], ..., [startN, endN], where each startX and endX variables have ranges. There are presence variables P1, P2, ..., PN.

There is a constraint that says ((endX - startX) >= 3).OnlyEnforceIf(PX) . I.e., if the interval X is present, it must be of length at least 3.

Now you want to pick a subset (possibly all) of the intervals, start times, end times, such that there are at least 2 present at a time, if any are present at all. Furthermore, for any time that 2 or more are present, the length of time that at least 2 are present is at least 3.

So if you had this data, representing the ranges of the intervals:
I1 = [1, 12], I2 = [2, 6], I3 = [5, 15], I4= [10, 20], I5 = [1, 30]
a valid schedule would be
I1 = I2 = [2, 6], I3 = I4= [10, 15]
or you could take that schedule and add I5=[2,6] OR I5=[10,15], and that would still be valid.

[lperron]

OK. Training constraint or transfer constraint.
For training, it is usually a bipartite graph. For transfer, the set of useful overlapping constraint is limited, like per machine, or geographically.

Anyway, you have pairs of potentially overlapping interval, and one or more of them must be true.

So, ((endX - startX) >= 3).OnlyEnforceIf(PX)

I would prefer sizeX >= pX * 3. Better relaxation.

For the min overlap part, getting inspiration from https://github.com/google/or-tools/blob/stable/ortools/sat/docs/scheduling.md#detecting-if-two-intervals-overlap , I am sure you can tweak the formula to add the min overlap distance.

then for each pair, have a Boolean b that indicates if the two intervals overlap with the correct min overlap, then b implies both presence, and implies the min overlap.

Then for each trainee task, presence => bool_or(trainer_overlap_booleans)

Did I get it right ?

[Dr-Irv]

then for each pair, have a Boolean b that indicates if the two intervals overlap with the correct min overlap, then b implies both presence, and implies the min overlap.

I did consider that model, but creating a boolean for each pair works when the minimum is 2, but when the minimum is 3, then you have to do it for each triple. If there are 100 intervals, you've now created almost 1,000,000 booleans.

That's why I liked the CPLEX interface using either cumul_range() (https://ibmdecisionoptimization.github.io/docplex-doc/cp/docplex.cp.modeler.py.html#docplex.cp.modeler.cumul_range) or always_in() (https://ibmdecisionoptimization.github.io/docplex-doc/cp/docplex.cp.modeler.py.html#docplex.cp.modeler.always_in), where a minimum can be specified.

[lperron]

If the intervals with the min requirements are disjoint, a reservoir can do the trick.
If you need 3, replace your +1, -1 events by a -2, +2. This way, with a minimum of zero, you are sure there are always 2 tasks active during the task.

[Dr-Irv]

If the intervals with the min requirements are disjoint, a reservoir can do the trick.

They are not disjoint.

If you need 3, replace your +1, -1 events by a -2, +2. This way, with a minimum of zero, you are sure there are always 2 tasks active during the task.

Problem with the reservoir is that the minimums have to be non-positive, and we need a minimum of 2, 3, 4, etc., dependent on the data.