Originally posted by: Talena

Originally posted by: PhilippeLaborie

Hi Felix,

I don't think there is any direct way for doing that.

Maybe we can take a step backward: why do you need this cumul for? What type of constraint will you post on this cumul? 

Also, I suppose that you do not want to do this only for one pair of intervals but more globally on a set of intervals x1,...,xn, right?

In this case, if say you have p intervals globally overlap at a time-point t, do you really want the cumul function at t be equal to p*(p-1)/2 (that is the number of pairs of intervals overlapping at t) ?

Philippe

Originally posted by: Talena

Hi Philippe,

first of all thanks for your quick answer.

} }

Thanks

Felix

Originally posted by: PhilippeLaborie

Yes, the description of the problem helps to have a more global view. But I still have my two questions:

- How do you compute the additional penalty if there are more than two tasks executing at the same time ? Or maybe this is not allowed ...

- How do you plan to constrain the total cumul function ? Will it just be some maximum level of 'mental resource' like totalCumul <= Constant ?

Also: 

- Beside the overlap, does each task contribute with the same amount to the total cumul function ? Or do you have some weights so that some tasks contribute more than others ?

In fact I'm still missing the exact mathematical formulation of how the total cumul is defined and how it is constrained.

This is a very interesting problem by the way.

Originally posted by: Talena

- How do you compute the additional penalty if there are more than two tasks executing at the same time ? Or maybe this is not allowed ...

This is not allowed at that point, but could be implemented in the future.

- How do you plan to constrain the total cumul function ? Will it just be some maximum level of 'mental resource' like totalCumul <= Constant ?

The total cumul function should be constrained by a constant how you mentioned it.

- Beside the overlap, does each task contribute with the same amount to the total cumul function ? Or do you have some weights so that some tasks contribute more than others ?

Each Task should contribute to total cumul with an individual value. I haven't implemented this yet but should happen on thursday.

 I have therefore indicated this by the 1 in Line 3 ->  c += IloPulse(pilotTasks[i],1);  

Originally posted by: PhilippeLaborie

Ok. So let's suppose you cannot have more than two tasks executing at the same time.

But let's consider that each task has a particular contribution to the cumul.

If you have a task of contribution w1 overlapping a task of contribution w2, I understand that the total contribution over the intersection of the two intervals is larger than w1+w2, but what is the formula to compute it? I'm still missing this.

Originally posted by: Talena

In addition to the demand values w1 and w2, there is a conflict value that is calculated before processing by "cp optimizer". It is specific to each overlapping pair of tasks. During runtime you only need to know which two tasks overlap and add the conflict value "v(w1,w2)" to the demand values "w1+w2" so the total pulse height is calculated with "w1+w2+v(w1,w2) = c".

Originally posted by: PhilippeLaborie

Do you have a particular form for v(w1,w2) ? in particular, is it separable of the form f(w1)+f(w2)+cst for instance. I'm asking because if it is the case you can think of efficient formulations.

Originally posted by: Talena

No it is unfortunately not separable.
The demand values w1 and w2 consist of demand vectors. The demand value is the average of the vector entries.
The conflict value v(w1/w2) is calculated using a conflict matrix. The individual components of the conflict value are selected according to whether values from the demand vectors overlap in the conflict component (see example). These individual components are then added together to form a conflict value.
I have attached a simple example. A 2x2 conflict matrix and demand vectors with 2 entries are used. In real terms an 8x8 matrix and 8 entries per demand vector are used.

Originally posted by: PhilippeLaborie

Thanks for the precision.

Indeed, the computation of the conflict value is not separable so it is difficult to handle this using cumul functions only.

Unless I'm missing other important parts of the problem, it seems that the computation of the total contribution of two tasks is only used to decide whether or not the two tasks can overlap (I'm obviously assuming here that you cannot have more than two tasks overlapping). 

Thus, from the set of tasks in the input you could precompute all the pairs (x,y) that cannot overlap. A naive approach can be to post non-overlapping constraints between all these pairs (like: overlapLength(x,y)==0). 

If the number of pairs is too large, you can also compact this "non-intersection" graph by aggregating some of the arcs of the graph into a more global constraint:

• clique => noOverlap constraint on a set of tasks
• threshold graph (https://en.wikipedia.org/wiki/Threshold_graph) => cumul function
• complementary of interval graph (https://en.wikipedia.org/wiki/Interval_graph) => stateFunction with constraints alwaysIn(function, vmin, vmax)

Maybe given the particular form of the non-overlapping constraint, one can show that the non-intersection graph can be easily decomposed into the above graphs …

Originally posted by: Talena

Thanks for the help so far.
I now calculate the interference values before optimization and can also decide which pairs may overlap and which may not using IloNoOverlap.
In order to generate a more dynamic structure, I now try to link the interference values with the overlap time and minimize them.
I multiplied the calculated interference values with the IloExprVar of IloOverlapLength(env, task1, task2). I try to minimize them. (see appendix)
However, I found an error in the overlap time. After the optimization I get the output and realize that the overlap times are always the duration of the first task independent of the length of the second task. The second Task can also be shorter than the overlapLength. I have already tried a lot (whether the length of the intervals is set correctly, for example) and cannot detect any errors.
Is it possible that I misunderstand IloOverlapLength and its functionality?

Originally posted by: PhilippeLaborie

The expression overlapLength(task1,task2) returns the length of the intersection between task1 and task2 when intervals task1 and task2 are both present. So I suppose that this is the definition that you expect. 

> The second Task can also be shorter than the overlapLength.

This is clearly impossible, indeed. Can you show an instance of overlapLength, with the values of the two intervals and the value returned by the overlapLength expression?

There is something that could be clarified in your formulation:

auto overlap = IloOverlapLength(env, pilotTasks[i], pilotTasks[j]);
IloNumExprArg overlapValue = totalInference * overlap;

First, I don't think you should use IloNumExprArg at all. This type is not supposed to be used in the formulations. See: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.9.0/ilog.odms.cpo.help/CP_Optimizer/User_manual/topics/model_vars_expr.html : Note that the parent classes IloIntExprArg and IloNumExprArg are used internally by Concert Technology to build expressions. You should not use IloIntExprArg or IloNumExprArg directly.

And also instead of auto I would explicitly use the integer expression class. So:

IloIntExpr overlap = IloOverlapLength(env, pilotTasks[i], pilotTasks[j]);
IloNumExpr overlapValue = totalInference * overlap;

I'm not sure this is related with the problem but in any case it will be clearer.

Also if I remember well, we had a bug in overlapLength expression but it was fixed several versions ago. Which version of CP Optimizer are you using?

If you are using a recent version (12.8 or 12.9) and still have the problem, could you try to generate a .cpo file of your model that illustrates the problem (ideally, as small as possible) ?

Originally posted by: Talena

We have recently updated to 12.9.
I added the notes regarding "auto" and "IloNumExprArg" and then exported a .cpo file (see attachment).
The relevant intervals are marked with "PT:". Here you can also see the length. As an objective, the overlaps of these PT intervals are multiplied by the demand values and then minimized. This looks a bit confusing, because there can be a lot of overlaps.

Here the overlap values (not multiplied by the demand) can be greater than the length of the respective "PT:" intervals and that should probably not be so.

Originally posted by: PhilippeLaborie

On this instance, could you find one of the pairs of interval variables for which, in the solution, the overlapLength value is not the one you would expect? (It is not so easy to do with the .cpo file only)

As a side note, I noticed that in the objective function you have both overlapLength(x,y) and overlapLength(y,x). If you could factorize the two, it would reduce the size of the expression by half and propagate a bit more. 

Originally posted by: Talena

For example, the overlap of "PT:ViewImage_B416" = intervalVar(length=30);" and "PT:ConfirmTargetStatus_B415" = intervalVar(length=2);". I would expect a maximum overlap of 2 here, because that's the length of the second interval. However, here I get 30 as the result, the length of the first interval.
In general, I always get the interval length of the x for overlapLength(x,y).

Originally posted by: PhilippeLaborie

This is strange.

When I run the .cpo you attached I get a solution at total cost 6647.750

The cost decomposes as follows:

• sum of end times: 5944
• sum of overlap length :  703.7500

When I look at the overlap length expressions with non-nun value in the solution, I get this ones (I first put the value of the overlap length, then the weight:

WeaponSelection_B410__CheckWeaponBasket_B328:     3 * 16.375
CheckWeaponBasket_B328__WeaponSelection_B410:     3 * 16.375
ViewImage_B416__ViewImage_B3213:                 14 * 19.9
ViewImage_B3213__ViewImage_B416:                 14 * 19.9
ConfirmTargetStatus_B3212__ViewImage_B416:        2 * 12.075000000000001
ViewImage_B416__ConfirmTargetStatus_B3212:        2 * 12.075000000000001

I checked and it seems that the value of the overlap length is correct, and it exactly sums up to 703.7500.

Do you have a different value for the objective function? Could you explain how you come to the conclusion that the value of some overlapLength is wrong given the interval values?

Here is the value of the interval variables in the solution I get:

TASK:ENGAGE9[1: 315 -- 1 --> 316]
TASK: ENGAGE worker 0[1: 315 -- 1 --> 316]
TASK: ENGAGE worker 1[0]
TASK: ENGAGE worker 2[0]
TASK: ENGAGE worker 3@4[0]
TASK:HIT_ASSESMENT10[1: 381 -- 10 --> 391]
TASK: HIT_ASSESMENT worker 0[0]
TASK: HIT_ASSESMENT worker 1[0]
TASK: HIT_ASSESMENT worker 2[1: 381 -- 10 --> 391]
TASK: HIT_ASSESMENT worker 3@11[0]
TASK:INVESTIGATE11[1: 222 -- 30 --> 252]
TASK: INVESTIGATE worker 0[0]
TASK: INVESTIGATE worker 1[0]
TASK: INVESTIGATE worker 2[1: 222 -- 30 --> 252]
TASK: INVESTIGATE worker 3@18[0]
TASK:INVESTIGATE0[1: 206 -- 30 --> 236]
TASK: INVESTIGATE worker 3@22[1: 206 -- 30 --> 236]
TASK:ENGAGE1[1: 305 -- 1 --> 306]
TASK: ENGAGE worker 3@26[1: 305 -- 1 --> 306]
TASK:HIT_ASSESMENT2[1: 366 -- 10 --> 376]
TASK: HIT_ASSESMENT worker 3@30[1: 366 -- 10 --> 376]
TASK:STARTTASK3[1: 0 -- 1 --> 1]
TASK: STARTTASK worker 0[1: 0 -- 1 --> 1]
TASK:STARTTASK4[1: 0 -- 1 --> 1]
TASK: STARTTASK worker 1[1: 0 -- 1 --> 1]
TASK:STARTTASK5[1: 0 -- 1 --> 1]
TASK: STARTTASK worker 2[1: 0 -- 1 --> 1]
TASK:STARTTASK6[1: 0 -- 1 --> 1]
TASK: STARTTASK worker 3[1: 0 -- 1 --> 1]
TASK:STARTTASK7[1: 0 -- 1 --> 1]
TASK: STARTTASK worker 4[1: 0 -- 1 --> 1]
TASK:STARTTASK8[1: 0 -- 1 --> 1]
TASK: STARTTASK worker 5[1: 0 -- 1 --> 1]
PT:WeaponSelection_B327[1: 256 -- 3 --> 259]
PT:CheckTargetPosition_B329[1: 259 -- 3 --> 262]
PT:CheckWeaponBasket_B328[1: 262 -- 20 --> 282]
PT:monitorWeaponEngagement_B3210[1: 305 -- 8 --> 313]
PT:VerifyDestruction_B3211[1: 366 -- 15 --> 381]
PT:ViewImage_B3213[1: 206 -- 30 --> 236]
PT:ConfirmTargetStatus_B3212[1: 236 -- 2 --> 238]
PT:WeaponSelection_B410[1: 272 -- 3 --> 275]
PT:CheckTargetPosition_B412[1: 282 -- 3 --> 285]
PT:CheckWeaponBasket_B411[1: 285 -- 20 --> 305]
PT:monitorWeaponEngagement_B413[1: 315 -- 8 --> 323]
PT:VerifyDestruction_B414[1: 381 -- 15 --> 396]
PT:ViewImage_B416[1: 222 -- 30 --> 252]
PT:ConfirmTargetStatus_B415[1: 252 -- 2 --> 254]
mission[1: 0 -- 391 --> 391]
pilot[1: 206 -- 190 --> 396]

For instance, the two interval variables you mention are fixed to:

PT:ViewImage_B416[1: 222 -- 30 --> 252]
PT:ConfirmTargetStatus_B415[1: 252 -- 2 --> 254]

And the overlapLength expressions on these 2 intervals have value 0 as expected.

Originally posted by: Talena

Am I just wrongly accessing the values of the overlap?
I access the values of the overlap with cp.getValue(b) and while b is the IloNumExpr of IloOverlapLength. (see Attachment)

Originally posted by: PhilippeLaborie

So indeed, there is an issue with the evaluation of the overlapLength expression, there is a typo and it systematically returns the length of the first interval!

The good new is that there is no problem in the search (the value of the objective and the values of the interval variables are correct), it is just when you try to evaluate the overlapLength expression on the solution.

So an easy work around is to re-implement the evaluation yourself, which is very easy:

IloInt EvaluateOverlapLength(IloCP cp, IloIntervalVar x1, IloIntervalVar x2) {
  IloInt s1 = cp.getStart(x1);
  IloInt e1 = cp.getEnd(x1);
  IloInt s2 = cp.getStart(x2);
  IloInt e2 = cp.getEnd(x2);
  return IloMax(0, IloMin(e1,e2)-IloMax(s1,s2));
}

And then you call EvaluateOverlapLength(cp,itv1,itv2) instead of cp.getValue(IloOverlapLength(itv1,itv2)).

This issue will of course be fixed in next release / fix pack.

Thanks for finding it.