Decision Optimization

Originally posted by: Vgoel77

As part of my CP model, I need to calculate the area under a cumul function that represents losses over time. The cumulative loss has to be minimized. I appreciate any help in figuring out how to calculate the area under the cumul function.

Here is the problem
Need to schedule withdrawals from a tank. each withdrawal is of constant amount and takes a unit of time. there are constraints on the withdrawal schedule that are not relevant.
Tank inventory should be positive and bounded by tank capacity. Tank gets pre-specified input of material in each time period. Overflow from tank (due to fixed input profile and inability to withdraw material in time) is considered a loss. Objective is to schedule the withdrawals such that total losses are minimized.

Pseudocode
w[i]: interval variables
p: cum function (fixed) for input in tank
ui: cum function for unconstrained inventory
i: cum function for inventory
i0: scalar for initial inventory
o: cum function for overflow
s: (fixed) size of withdrawal
z: cum function for withdrawn volume
c: capacity of tank
t0,tmax: range of time horizon

z = sum_i step(w[i])*s
ui = i0 + p - z
o = max(0,ui-c)
i = ui - o
alwaysIn(i,t0,tmax,0,c)

objective: minimize total overflow (= area under cum function for "o")

How do I develop an expression to calculate this area?

And a related question: if I had to calculate the value of z at the end of the time horizon, can I use some inbuilt function or do I need to calculate as sum_i presenceOf(w[i]) \times s

Thanks
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

Hello,
There is no direct way to get this area under CumulFunction in CP Optimizer.

You could approximate this tank overflow by partitioning the schedule horizon into a set of contiguous time windows Aj=[Sj,Ej] and use an expression that measures the peak usage of the tank over the (fixed) time window Aj. For doing that you can introduce one interval variables aj for each time window Aj (with fixed start and end value) that contributes with a pulse of variable height hj and represents the "free" amount of tank assuming a max capacity Q (much bigger than the actual capacity C). The objective will be related with maximizing this free level. The peak tank level over Aj will be (Q-hj) and the max overflow over Aj will be max((Q-hj),C).

Pseudocode
w[i]: interval variables
p: cum function (fixed) for input in tank
z: cum function for withdrawn volume
ui: cum function for unconstrained inventory
a[j]: interval variables for time-windows (fixed start S[j] and end E[j])
h[j]: integer expression, height of contribution of intervals a[j]
C: capacity of tank
Q: large integer
f: cumul function measuring the "free" reservoir level under Q
u: cum function for measuring peak usage

z = sum_i step(w[i])*s
ui = i0 + p - z

f = sum_j pulse(a[j],0,Q-C)
h[j] = heightAtStart(f,a[j]); // <=Q-C so C<=Q-hj
u = ui + f

u <= Q;

objective (upper bound on the actual objective): sum_j (Ej-Sj)*(Q-h[j])

If you would introduce one interval a[j] per time unit (Ej-Sj=1), then you would get the exact objective. But of course that would introduce a huge number of decision variables (the heights h[j]).

This being said, I'm not expecting CP Optimizer to behave very well on this type of problem. These types of problems are often handled in two steps: a planning steps that roughtly allocates the activities to some time-buckets in order to balance the tank usage (and here, minimize tank overflow) followed by a detailed scheduling step that tries to schedule the activities in (or as close as possible to) the time-bucket they were allocated to and this steps handles more detailed scheduling constraints and objectives on the tasks. The CPLEX algorithm is particularly well adapted for the first step, whereas CP Optimizer is more adapted to the detailed scheduling step.

Philippe
#CPOptimizer
#DecisionOptimization

Originally posted by: Vgoel77

Philippe
Thanks for the reply. I am not quite sure that I understand your solution.
Issue
What prevents the solver from choosing f = 0 everywhere? Also, I am guessing that f refers to free volume under Q but above C (otherwise, free volume would range between 0 and Q)

Your solution did give me the following ideas though:
other solution 1
z = sum_i step(w[i])*s
ui = i0 + p - z
o = sum_j pulse(a[j],0,Q-C) // implicit overflow definition
h[j] = heightAtStart( o ,a[j]); // <=Q-C so C<=Q-hj
u = ui - o;
u <= C;

This model still has the problem that it could choose more overflow than neccessary and drive inventory down in some part of the horizon and "avoid" overflow in latter parts of the horizon. That could be overcome by changing the objective as
min sum_j (Ej-Sj)*h[j]*a[j] where a[j] is a weight factor and a[j] > aj-1

other solution 2
z = sum_i step(w[i])*s
ui = i0 + p - z

// calculate overflow
o = max(ui - C,0) // can we actually calculate max of two cum functions

//create extra cum function that is built up of a set of pulses and is equal to overflow; pulse heights will automatically be set equal to overflows

f = sum_j pulse(a[j],0,Q-C) // implicit overflow definition
f = o
h[j] = heightAtStart(f,a[j]); // <=Q-C so C<=Q-hj

u = ui - o;
u <= C; // redundant

What do you think?
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

> What prevents the solver from choosing f = 0 everywhere? Also, I am guessing that f
> refers to free volume under Q but above C (otherwise, free volume would range between 0 and Q)

It is the objective that prevents choosing f=0:

f = sum_j pulse(a[j],0,Q-C)
h[j] = heightAtStart(f,a[j]); // <=Q-C so C<=Q-hj
objective (upper bound on the actual objective): sum_j (Ej-Sj)*(Q-h[j])

The objective tells to choose h[j] as big as possible, that is f (free volume between C and Q) as big as possible.

By the way, there is a typo in the objective, it should read:
objective (upper bound on the actual objective): sum_j (Ej-Sj)*(Q-h[j]-C)

> can we actually calculate max of two cum functions?

No.

Philippe
#CPOptimizer
#DecisionOptimization