On interval variables and optional interval variables

[tias]

So Interval variables and Optional interval variables are the only features of state-of-the-art CP solvers that our library does not yet support...

We don't want to add them as primitive variables because then they can be used in any expression, which requires working out the full semantics and code-wise this would be a lot of special casing etc.

We created #121 DirectVariable prototype for them, to generically support ortools/CP's interval variables, and we actually use it in some projects with companies. But it is also quite some technical debt should we include it in the main code.

But because we do want them for flexible jobshop (e.g. README) and work we do, I gave it some more thought:

So OrTools has 2 types of IntervalVariables (well, also can create versions with implicit 'end', but lets ignore that for now)

• NewIntervalVar
• NewOptionalIntervalVar

And those are used in just 3 constraints of OrTools:

• AddCumulative
• AddNoOverlap -- special case of Cumulative where demand and capacity=1
• AddNoOverlap2D -- special case of 2D NoOverlap

Now because these are all special cases of each other, this means that they will never appear together in a model.

So an IntervalVar is not really a variable in the expression-tree sense, its just a construct to post either a Cumul, NoOv or NoOv2D over...

So if its only to the purpose of these constraints, we can just create constraints for each combo; that's just 4 combo's if we ignore the binpacking NoOv2D for now:

• Cumulative(start, dur, end, demand, capa)
• NoOverlap(start, dur, end)
• CumulativeOptional(start, dur, end, demand, capa, option)
• NoOverlap(start, dur, end, option)

And of those 4, we already have the first two as globals... (although only Cumulative is in the docs, a different TODO)

Now this does ignore one thing: creating an IntervalVar also enforces it to be an interval, e.g. start+dur=end. For solvers like OrTools that have IntervalVars, this is implicit when using our Cumulative (as we create the IntervalVar behind the scenes), but for a solver that decomposes this is not implicit...

So that means we also either need two more constraints:

• IsInterval(start, dur, end)
• IsOptionalInterval(start, dur, end, option)

or, we need to change the signature of the 4 constraints above to include an enforceInterval=True argument...

(the latter will avoid users using a solver that supports IntervalVars to still manually post start+dur=end; the former will mean that solvers with IntervalVars will have twice the interval variables created by our model, once in IsInterval, once in Cumulative, which I hope will be very little overhead in practice)

---

Does this reasoning make sense?

Do we want to add the 2Optional globals and hence abort the DirectVar approach?

Should we have IsInterval's, or have an enforeInterval argument, or maybe even both?

Discussion welcome...

[IgnaceBleukx]

I fully agree we should have a more generic approach for supporting these nice scheduling-specific globals.
Special-casing the few globals that we currently have, does sound like nice idea! The option argument can just be optional (:-)) and have a default of None or True. Alternatively, we can also subclass Cumulative and NoOverlap, that would keep the transformation stack a little bit cleaner, as we don't have to check whether there are Optional vars in the Cumulative in __add__ -- ok so actually I think I prefer subclassing.

Now, we have to be careful regarding semantics of this optionality in our global constraints, as typically a user can re-use the same interval variable in multiple constraints. So, when it is non-present, it is globally not present in the model.
In your proposed approach this is also easy to enforce (just use the same Boolean for the option argument in all constraints where you use the optional interval), but we have to make this very explicit in the documentation.

Regarding the decomposition, I don't think much will change!
In the current Cumulative decomposition, we enforce start + dur == end and if this is not true for any of the "intervals", Cumulative is not satisfied.
In the OptCumulative version, this part of the decomposition will simply become option -> (start + dur == end).
To "count" the required resources at any timestep, we need to include the Boolean in that computation too:

for t in range(horizon):
    req_at_t = intvar(0,..., shape=len(start))
    constraining += [option.implies(req_at_t == cp.sum(demand * (start <= t & end > t)))]

Probably the decomposition of NoOverlap will require a little bit more thought, but should be doable as well.

[tias]

Alright, let's split it up:

Maybe first clarify that the 'option' argument is supposed to be a list of boolvars. Not a bool True/False (modeller needs access to the option vars)

Single function with subclassing or multiple functions:

Wile it might seem elegent, I think there is a hidden complication for merging Cumulative(start,dur,end) and CumulativeOptional(star, dur, end, opt) into a single Cumulative(star, dur, end, opt=None|opt). It is handled by different global constraints in the solver; while we can special-case this in the decompose() function, also in each solver we will have to special case it, and in our decompose_globals() transformation where we will have to have a custom check to see if a solver supports one or both (and which one is needed now).

We also don't have AllDifferent(arr, except=None|v). So, I would keep the 2 new globals separately really.

decomposition has 'interval' requirement

I'm surprised to read our current cumulative decomposition also always enforces start+dur=end. Is that what people would understand with the decomposition? Is that what a solver would implement? For me, the constraint is only on the demand... for those demand-moments between start and end (if any)...

I do think for this one, we could add an argument enforceInterval=True|False which would post that, but I don't think that is the default. If a solver has native support without interval vars, the docs would say so and on enforceInterval=True we would use its mechanism to also enforce that...

decomposition implementatoin of CumulativeOptional and NoOverlaOptiona

Great that it would be so elegant. For NoOverlap, you can replace demand/capacity with constant 1 and simplify accordingly so that should be straightforward too then.

[IgnaceBleukx]

Ok so indeed the vector of Boolvars is also how I envisioned it; and we agree subclassing is the right way forward ; )

Decomposition
Well, by enforcing start + dur == end is also to they way that the catalog describes it:
https://sofdem.github.io/gccat/gccat/Ccumulative.html

So I think it makes sense to follow that.

An alternative would be to not include end in the arguments of Cumulative, and let the user do this himself, but I don't think that is the prefered way.

Decomp implemenation
For NoOverlap we can indeed alter the decomposition, to basically represent a unit-resource Cumulative constaint and then it would be trivial to add the optionality of tasks.
Currently, we decompose it with pairwise no-overlaps between each tasks; we should probably check what is more efficient.

[tias]

OK, I' propose we split this into two parts:

1. add an IsInterval() global, add 'ensure_interval=True' to NoOverlap and Cumulative. This refactors our status quo, rather low-hanging fruit. I will do this, it will clean up our code example in the README.

2. add an IsIntevalOptional() global, add a CumulativeOptional() global and a NoOverlapOptional() global. Might or might not need some experiments to chose a decomposition (task-based or time-based); requires new tests in any case.

[IgnaceBleukx]

I made a draft PR #676 implementing these ideas.
It turned out the neat "demand * is_present" decomposition is unfortunately not valid for non-positive contexts... So had to make an actual decomposition to elementary constraints instead. Let's move any further discussion to the PR?