Originally posted by: SaumyaB

Hi, 

I am trying to formulate a variant of RCPSP using Java and CP Optimizer. Is there any CP function in java to access value of the pulse function (resource usage) at a given time step t, so I can try to formulate the resource constraint for all such time steps. I understand that CP has a function called cumulFunctionValue in OPL but this can be used only after the solution is obtained. Due to some reason, using the pulse function and enforcing the cumulative usage <= capacity as a soft-constraint (i.e., adding it as a cost/ penalty term in the objective) is giving discrepancies in the number of resource violations.

Partial code below:

usage.add(cp.pulse(actInterval[i][j], act.resourceRequired[k]));                                                             // Looping over all interval variables indexed by [i][j] and resources k 

cp.add(cp.le(usage, cp.sum(cost, instance.resourceCapacity[k]))).setName("capacity constraint");   // Looping over all resources k

Originally posted by: PhilippeLaborie

The constraints you posted (usage <= ResourceCapacity + costVar) says that at any time point t, you have usage[t]<=ResourceCapacity + costVar. Thus if you minimize costVar, you minimize the peak usage of the resource, not the area between usage and the constant function ResourceCapacity + costVar. This explains the discrepancy with what you expect.

If you want to measure the sum of the extra resource consumption at each time-point, you would have to discretize time and will loose most of the advantages of CP Optimizer (but it may still be ok depending on your problem). 

You can also discretize time with a larger granularity than the time unit and consider a period P>=1. You can have an expression that measures the peak extra-consumption for every period P (so on [0,P), [P,2P), [2P,3P),...). Then in the model, you create one additional interval variable free[i] for each period with fixed start time (i*P) and end time ((i+1)*P). Suppose that Max is an integer denoting the resource capacity you can by no way exceed (you need to have Max>=ResourceCapacity; Max can be an arbitrary large number but depending on your application, you may also consider a really hard max value for the resource). Then, free[i] will reserve (with a pulse) a certain quality of the extra resource (between 0 and Max-ResourceCapacity) that will not be consumed over the ith period. So free[i] will contribute to the cumul function with a variable range in 0..Max-ResourceCapacity and you will try to maximize the height of these pulses.

So you have a cumul function:

f = usage + sum(i) pulse(free[i],0..Max-ResourceCapacity);

You have:

f <= Max

The peak of over-consumption of the resource on period i is the integer expression : Max - heightAtStart(free[i],f)

So you want to minimize sum(i) ( Max - heightAtStart(free[i],f) )

What you ideally would like is to do P=1, it will work but will probably result in a large number of periods. And the model you sketched in your question is the same as the special case where you only have one interval (P equal to the whole horizon of the schedule).

Originally posted by: SaumyaB

Hi Philippe,

Thanks for the step-by-step breakdown of the problem solution. 

Regards,

Saumya

Originally posted by: SaumyaB

Hi Philippe,

If I understand this correctly, by area between usage and the constant function ResourceCapacity + costVar, do you imply that this term is more related to the resource violations/over-consumption?

I am able to calculate the peak of over-consumption of a resource k with the expression Max - heightAtStart(free[i], f). However, trying different values P>=1 gives me different objective values. Some of which are desirable, some are not. I am not clear as to why this is so. My problem is a bi-objective one with a weight associated with the over-consumption term. For different P values (like P=1, 10, 100 etc.), I did test runs keeping everything in the model the same (including this weight term).

Also, after obtaining the schedule, I have a code that counts the unique violations happening at any resource at any time point. I am not clear if there is a way to re-reconcile the counts I get from the above mentioned approach and this count (ex, what is the value of P I should set). Any help on this would be greatly appreciated. Thanks.

Originally posted by: PhilippeLaborie

> If I understand this correctly, by area between usage and the constant function ResourceCapacity + costVar, do you imply that this term is more related to the resource violations/over-consumption?

My statement was not clear. I meant the area of the function "usage" that exceeds ResourceCapacity, so sum(t) max(0, usage(t)-ResourceCapacity)

From your description I understand that your objective is to minimize this criterion OBJ_1 = sum(t) max(0, usage(t)-ResourceCapacity)

> I am able to calculate the peak of over-consumption of a resource k with the expression Max - heightAtStart(free[i], f). However, trying different values P>=1 gives me different objective values. Some of which are desirable, some are not. I am not clear as to why this is so. My problem is a bi-objective one with a weight associated with the over-consumption term. For different P values (like P=1, 10, 100 etc.), I did test runs keeping everything in the model the same (including this weight term).

sum(i) ( Max - heightAtStart(free[i],f) ) is the sum of all overconsumption of the peak usage of each period T, so if you multiply by T you will get an over-estimation of your actual objective OBJ_1.

OBJP_T = T * sum(i) ( Max - heightAtStart(free[i],f) )

The optimal value OBJP*_T for OBJP_T is an upper estimation of OBJ*_1, but both expressions coincides when T=1 (provided of course that the CP Optimizer model is able to reach the optimal solution)

It is pretty easy to see if you draw the function 'usage', the periodic intervals of period T and the different areas.

Philippe

Originally posted by: SaumyaB

Hi Philippe,

I am able to plot the function usage Vs the periodic intervals of T. Thanks for the detailed explanation. Appreciate all the help on this.

Regards,

Saumya

Originally posted by: SaumyaB

Hi Philippe,

Regarding finding out the resources where violations happen, I have two ways to do this. One is to plot the function usage Vs the periodic intervals of T for a resource, using the approach you mentioned (CP approach). Another way that I use is a code that counts violations happening at any resource at any time point from the output schedule. However, I notice a discrepancy in these two. CP approach does not capture some resources where violations happen. 

Such cases happen at a time point which is the very last time point when one activity uses that resource and this time point is also the very first time point of another activity that has just started to use that same resource. So in such cases, the usage from CP approach comes out to be 1 instead of 2.

Could it be because the pulse function is defined on an half open interval? Since pulse(u, v, h) is a function F such that F(t) = h if t belongs to [u, v), F(t) = 0 otherwise as per this link: 

https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.1/ilog.odms.ide.help/OPL_Studio/opllangref/topics/opl_langref_scheduling_cumulfunc.html

Appreciate any inputs on this. Thanks.

- Saumya

Originally posted by: PhilippeLaborie

Exactly. Intervals are semi-open on the right.So if two intervals a and b have a constraint endAtStart(a,b) and bth require the same resource, say a cumul of maximal level 1, both contributing with a pulse of height 1, then the problem is feasible. In most problems, this convention helps to avoid many error prone +-1.

Philippe

Originally posted by: SaumyaB

Thanks a lot for the clarification. Appreciate all the help on this.

-Saumya