Hi,

I have got a number of interval variables which are linked to another interval via the span constraint.

These interval variables have a type (representing a resource) and I need to make sure that the number of concurrent usages of the resource is respected.

To that end, I'd use a cumul / pulse function. However, I have the additional constraint that the spanning interval represents a container for the resources - if I pulse one of the intervals in the container, I would like to pulse the whole container interval.

To give you a simplified example:

from docplex.cp import model as cp

model = cp.CpoModel()

intervals = [cp.interval_var(length=1) for _ in range(3)]
seq = cp.sequence_var(vars=intervals, types=[0, 1, 0])

spanning_interval = cp.interval_var()
model.add(cp.span(interval=spanning_interval, array=intervals))​

Pulsing a single interval is easy and I can use it to block the resource

f = 0
for it, t in zip(seq.get_interval_variables(), seq.get_types()):
    if t == 1:
        f += cp.pulse(interval=it, height=1)

Now, how can I pulse the spanning interval, if any of the critical resources is present?

I tried to do it via a multiplication of pulse functions, but that does not work.

f = 0
for it, t in zip(seq.get_interval_variables(), seq.get_types()):
    if t == 1:
        f += cp.pulse(interval=it, height=1) * cp.pulse(interval=spanning_interval, height=1)

Note that in the real model, the intervals in the container are actually optional and linked to another interval via the alternative constraint, so the trivial solution of pulsing the spanned interval only does not work, unfortunately.

Is there some alternative approach? Some kind of "conditional" pulsing, perhaps?

Thanks and best regards
Sebastian

------------------------------
Sebastian Bayer
------------------------------

#DecisionOptimization

Hi,
There might be different ways to model this.
The first thing that came to my mind was to create an optional interval with the same start and end time as the spanning interval, and whose presence if conditioned on the presence of at least one of the type==1 intervals.
This would look like this:
optional_spanning_interval = cp.interval_var(name='optional_spanning_interval', optional=True)
OR_expr = (model.sum([cp.presence_of(it) for it, t in zip(seq.get_interval_variables(), seq.get_types()) if t == 1]) >= 1)
model.add(cp.presence_of(optional_spanning_interval) == OR_expr)
model.add(cp.start_of(optional_spanning_interval) == cp.start_of(spanning_interval))
model.add(cp.end_of(optional_spanning_interval) == cp.end_of(spanning_interval))

Then, you need to create an additional pulse for this new optional interval.
If "optional_spanning_interval" is present then the pulse function is enabled.
For example:
container = 0
container += pulse(interval=optional_spanning_interval, height=1)

Is this what you are trying to do ?
Best regards,
Hugues

------------------------------
Hugues Juille
------------------------------

Hi Hugues,

yes, that approach accomplishes indeed what I would like to see. I'm a bit worried about scalability, though.
In practice, the number of containers is between 50 and 200 and the number of resources is between 50 and 300.

In the worst case, this would add 60,000 new interval variables. I still need to properly test it, but I think I could run into some scalability issue with that approach.

In some old presentation I found this comment. Has there perhaps already been progress in this area?




Regards
Sebastian

------------------------------
Sebastian Bayer
------------------------------

Original Message:
Sent: Thu February 17, 2022 04:58 AM
From: Hugues Juille
Subject: Pulse a spanned interval variable

Hi,
There might be different ways to model this.
The first thing that came to my mind was to create an optional interval with the same start and end time as the spanning interval, and whose presence if conditioned on the presence of at least one of the type==1 intervals.
This would look like this:
optional_spanning_interval = cp.interval_var(name='optional_spanning_interval', optional=True)
OR_expr = (model.sum([cp.presence_of(it) for it, t in zip(seq.get_interval_variables(), seq.get_types()) if t == 1]) >= 1)
model.add(cp.presence_of(optional_spanning_interval) == OR_expr)
model.add(cp.start_of(optional_spanning_interval) == cp.start_of(spanning_interval))
model.add(cp.end_of(optional_spanning_interval) == cp.end_of(spanning_interval))

Then, you need to create an additional pulse for this new optional interval.
If "optional_spanning_interval" is present then the pulse function is enabled.
For example:
container = 0
container += pulse(interval=optional_spanning_interval, height=1)

Is this what you are trying to do ?
Best regards,
Hugues

------------------------------
Hugues Juille
------------------------------

Hi Sebastian,
I think the  scaling issue needs to be assed experimentally. This is difficult to evaluate from the formulation.
Nothing new has been delivered regarding supported "algebra" for cumul functions. Only + and - are currently supported.

Looking at the formulation I proposed in my previous message, I missed 2 points:
- CPO supports the "any" constrained function that directly implements the OR expression,
- the equality constraints on "start" and "end" times is not working properly in the case where the optional_spanning_interval is not present. Instead, one should use "start_at_start" and "end_at_end" constraints.

The new formulation looks like this:
optional_spanning_interval = cp.interval_var(name='optional_spanning_interval', optional=True)
OR_expr = cp.any([cp.presence_of(it) for it, t in zip(seq.get_interval_variables(), seq.get_types()) if t == 1])
model.add(cp.presence_of(optional_spanning_interval) == OR_expr)
model.add(cp.start_at_start(optional_spanning_interval, spanning_interval))
model.add(cp.end_at_end(optional_spanning_interval, spanning_interval))

Best regards,
Hugues

------------------------------
Hugues Juille
------------------------------

Original Message:
Sent: Thu February 17, 2022 07:43 AM
From: Sebastian Bayer
Subject: Pulse a spanned interval variable

Hi Hugues,

yes, that approach accomplishes indeed what I would like to see. I'm a bit worried about scalability, though.
In practice, the number of containers is between 50 and 200 and the number of resources is between 50 and 300.

In the worst case, this would add 60,000 new interval variables. I still need to properly test it, but I think I could run into some scalability issue with that approach.

In some old presentation I found this comment. Has there perhaps already been progress in this area?




Regards
Sebastian

------------------------------
Sebastian Bayer
------------------------------


Original Message:
Sent: Thu February 17, 2022 04:58 AM
From: Hugues Juille
Subject: Pulse a spanned interval variable

Hi,
There might be different ways to model this.
The first thing that came to my mind was to create an optional interval with the same start and end time as the spanning interval, and whose presence if conditioned on the presence of at least one of the type==1 intervals.
This would look like this:
optional_spanning_interval = cp.interval_var(name='optional_spanning_interval', optional=True)
OR_expr = (model.sum([cp.presence_of(it) for it, t in zip(seq.get_interval_variables(), seq.get_types()) if t == 1]) >= 1)
model.add(cp.presence_of(optional_spanning_interval) == OR_expr)
model.add(cp.start_of(optional_spanning_interval) == cp.start_of(spanning_interval))
model.add(cp.end_of(optional_spanning_interval) == cp.end_of(spanning_interval))

Then, you need to create an additional pulse for this new optional interval.
If "optional_spanning_interval" is present then the pulse function is enabled.
For example:
container = 0
container += pulse(interval=optional_spanning_interval, height=1)

Is this what you are trying to do ?
Best regards,
Hugues

------------------------------
Hugues Juille

Dear Hugues,

many thanks for the clarification and the updated constraints. I tested it, but unfortunately the performance decreases significantly with these constraints.
I have posted a more complete example here, maybe there is a general flaw in my approach.

Best regards
Sebastian


------------------------------
Sebastian Bayer
------------------------------

Original Message:
Sent: Tue February 22, 2022 07:15 AM
From: Hugues Juille
Subject: Pulse a spanned interval variable

Hi Sebastian,
I think the  scaling issue needs to be assed experimentally. This is difficult to evaluate from the formulation.
Nothing new has been delivered regarding supported "algebra" for cumul functions. Only + and - are currently supported.

Looking at the formulation I proposed in my previous message, I missed 2 points:
- CPO supports the "any" constrained function that directly implements the OR expression,
- the equality constraints on "start" and "end" times is not working properly in the case where the optional_spanning_interval is not present. Instead, one should use "start_at_start" and "end_at_end" constraints.

The new formulation looks like this:
optional_spanning_interval = cp.interval_var(name='optional_spanning_interval', optional=True)
OR_expr = cp.any([cp.presence_of(it) for it, t in zip(seq.get_interval_variables(), seq.get_types()) if t == 1])
model.add(cp.presence_of(optional_spanning_interval) == OR_expr)
model.add(cp.start_at_start(optional_spanning_interval, spanning_interval))
model.add(cp.end_at_end(optional_spanning_interval, spanning_interval))

Best regards,
Hugues

------------------------------
Hugues Juille
------------------------------


Original Message:
Sent: Thu February 17, 2022 07:43 AM
From: Sebastian Bayer
Subject: Pulse a spanned interval variable

Hi Hugues,

yes, that approach accomplishes indeed what I would like to see. I'm a bit worried about scalability, though.
In practice, the number of containers is between 50 and 200 and the number of resources is between 50 and 300.

In the worst case, this would add 60,000 new interval variables. I still need to properly test it, but I think I could run into some scalability issue with that approach.

In some old presentation I found this comment. Has there perhaps already been progress in this area?




Regards
Sebastian

------------------------------
Sebastian Bayer


Original Message:
Sent: Thu February 17, 2022 04:58 AM
From: Hugues Juille
Subject: Pulse a spanned interval variable

Hi,
There might be different ways to model this.
The first thing that came to my mind was to create an optional interval with the same start and end time as the spanning interval, and whose presence if conditioned on the presence of at least one of the type==1 intervals.
This would look like this:
optional_spanning_interval = cp.interval_var(name='optional_spanning_interval', optional=True)
OR_expr = (model.sum([cp.presence_of(it) for it, t in zip(seq.get_interval_variables(), seq.get_types()) if t == 1]) >= 1)
model.add(cp.presence_of(optional_spanning_interval) == OR_expr)
model.add(cp.start_of(optional_spanning_interval) == cp.start_of(spanning_interval))
model.add(cp.end_of(optional_spanning_interval) == cp.end_of(spanning_interval))

Then, you need to create an additional pulse for this new optional interval.
If "optional_spanning_interval" is present then the pulse function is enabled.
For example:
container = 0
container += pulse(interval=optional_spanning_interval, height=1)

Is this what you are trying to do ?
Best regards,
Hugues

------------------------------
Hugues Juille