# Decision Optimization

View Only

## Tracking Max/Min of Cumul Function within Fixed intervals

• #### 1.  Tracking Max/Min of Cumul Function within Fixed intervals

Posted Thu December 16, 2021 03:23 PM
Edited by Louis Luo Thu December 16, 2021 03:25 PM
Hi,

In CP Optimizer, I was wondering is there a way to track the maximum or minimum of a cumulative function within some fixed interval that is a subset of cumul function's domain?

For instance, say I have a cumul function representing one big resource from time 0 to time 100, and I want to add, to an objective function, two linear costs associated with the minimum/maximum value of this cumulative function from time intervals [10, 50] and [50, 80], respectively.

I am aware that I can track the max of a cumul function (f) over its entire domain by the simple expression "f <= x", where x is an integer variable, and similarly the minimum. For a subset of the domain, I see on the documentation [1] that perhaps I can do this with "AlwaysIn" constraint, but I found that its arguments "h_min" and "h_max" cannot be (integer) variables during implementation.

One idea is that perhaps I can decompose single resource into separate ones segmented by the start and end times of these fixed intervals (e.g. [0, 10], [10, 50], [50, 80], [80, 100]), but that would involve using "Alternative" constraint and creating more interval variables, which I am reluctant to do. Is there a better way to accomplish this?

[1] https://www.ibm.com/docs/en/icos/20.1.0?topic=concepts-cumul-functions-in-cp-optimizer

Thanks,
Louis

------------------------------
Louis Luo
------------------------------

• #### 2.  RE: Tracking Max/Min of Cumul Function within Fixed intervals

Posted Fri December 17, 2021 04:30 AM
Hi,

For instance,

using CP;

range r=1..3;

dvar interval itvs[i in 1..3] in i..i+5 size 5;

// 3 simple cumuls
cumulFunction  ci[i in r]=pulse(itvs[i],i);
cumulFunction ci4=pulse(0,10,100);

// sum of those 3 cumuls
cumulFunction sumc=sum(i in r) ci[i];
cumulFunction sumc2=ci[1]+ci[3]-ci[2]+ci4;

subject to
{
sumc<=10;
sumc2<=1000;
}​

works fine

Using this you could manage with what you need

------------------------------
[Alex] [Fleischer]
[EMEA CPLEX Optimization Technical Sales]
[IBM]
------------------------------

• #### 3.  RE: Tracking Max/Min of Cumul Function within Fixed intervals

Posted Fri December 17, 2021 02:39 PM
Edited by Louis Luo Sat December 18, 2021 01:00 AM
Hi Alex,

Thank you for your response. I am not sure if I can simply use the inequality as you have suggested, because the inequality implies the maximum/minimum over the entire time horizon of the cumul function, but I only want the max/min over some subset of the time horizon (i.e. local max/min).

I would like to append one more (complicating) details about the problem structure (that hopefully clarifies my intention):
• the start time of the jobs can be anywhere over the domain of the cumulative function of the sole resource
Also, to avoid confusion, I will refer to the fixed intervals of time as "zones" (e.g [10, 50] in the previous post). I will illustrate the problem in an example solution, where I would like to keep track of the max/min of the cumul function within a "zone".

Then, since the interval variables (representing jobs) can start anywhere in the domain of the cumul function, I found that I could not track the maximum or minimum of the cumul function as I would not know which jobs falls into the zone or outside of the zone.

For instance, for the following solution (where z denotes a zone and the resource has capacity of 6):
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Time Horizon id - - - - z z z z z z z - - - Time "Zone" Locations [ J1 ] [ J2 ] [ J3 ] Job Intervals (of fixed size) [ J4 ] 2 2 2 0 4 6 6 6 6 2 2 0 0 0 Cumul Function Value

Ideally, I would like to penalize any capacity of the resource not used to full over the time "zone". In this solution, I will penalize t = {5, 10, 11} only, as the "zone" starts at t = 5 and ends at t = 11. One approximation I can compromise with is to only penalize (the total resource capacity - maximum usage over the time zone), which may be simpler, hence motivating my original question.

Does this make sense?

------------------------------
Louis Luo
------------------------------

• #### 4.  RE: Tracking Max/Min of Cumul Function within Fixed intervals

Posted Sun December 19, 2021 03:17 PM
Going on with sum of cumuls, I would write

using CP;

int offset=100;
int s=10;
int e=50;
dvar int+ x in 0..1000;

dvar interval itvs[1..3] in 0..1000 size 10;
cumulFunction c=sum(i in 1..3) pulse(itvs[i],1);
cumulFunction c2=c+pulse(s,e,offset);

minimize x;

subject to
{
c<=1;
c2<=offset+x;
}​

where the goal is to minimize what is between s=10 and e=50

regards

------------------------------
[Alex] [Fleischer]
[EMEA CPLEX Optimization Technical Sales]
[IBM]
------------------------------