Originally posted by: SystemAdmin

[dgravot@noos.fr said:]

Assume I have a set of intervals named tasks.  One might wonder to know if at a given time point t , there are intervals in tasks that overlap the time slot [t,t+1)

therefore I currently compute an expression such as :


dexpr int overlap[t in horizon] = or(tk in tasks) (presenceOf(itvs[tk])==1 && startOf(itvs[tk])<=t && endOf(itvs[tk])>t);


Is there a better way , e.g more efficient in terms of propagation, to compute such indicator (maybe using cumulative function or state function) ?

Besides, running a tiny sample, I have some surprising result when I display the overlap expression

using CP;

range horizon = 0..10;
dvar interval itvs[i in 1..2] in horizon size 2;

dexpr int overlap[t in horizon] = or(tk in 1..2) (presenceOf(itvs[tk])==1 && startOf(itvs[tk])<=t && endOf(itvs[tk])>t);
constraints
{
noOverlap(itvs);
}

int nbslot = sum(t in horizon) overlap[t];
execute
{
writeln("number of covered slots ",nbslot);
writeln(overlap);
}


while the solution panel displays correctly :
itvs = [<1 0 2 2> <1 2 4 2>];

the scripting log panel shows :
number of covered slots 4
[1 1 0 0 0 0 0 0 0 0 0]

I would expect  [1 1 1 1 0 0 0 0 0 0 0] rather !

David
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[phlab said:]

Hello David,

The surprising display you get is probably caused by a bug in the evaluation of expressions during post-processing as the values of the expressions in the engine seem to be the correct ones. We are investigating ...

Looking at your model, my first reaction is to try to understand why you need an explicit enumeration of time ("t in horizon"). The modeling language for detailed scheduling in CP Optimizer is precisely here to try to avoid this explicit enumeration. I suppose you have a good reason for enumerating time, could you give some more details about it ? (there may be alternative models avoiding this enumeration and, if not, we will have an interesting use case).

If you really need this enumeration, you can either use the expressions you described but if there is n tasks and an horizon of h, there will be n*h constraints (startOf(...)<=t and endOf(...)>t) in these expressions. Note that you could slightly simplify the expression by using an "absence" value for the startOf and endOf expressions. Your expression can also be written:


dexpr int overlap[t in horizon] = or(tk in 1..2) (startOf(itvs[tk],0)<=t && endOf(itvs[tk],0)>t);


Indeed when the interval is absent, startOf(itv,0)=endOf(itv,0)=0 and the condition will be false.

You can also think of an alternative model where you create one optional interval used[t] of size 1 for each t in horizon that is fixed to start at t and use a cumul function to count the number of intervals from itvs executing at each time t. You can then constrain that when the cumul function is null at t, it forces used[t] to be absent (alwaysIn(cumul, used[t], 1, n)). This will not force used[t] to be present when the cumul is not nul. For that, you would have to use another set of intervals notUsed[t] that require alwaysIn(cumul, notUsed[t],0,0) and thus, will be absent when the cumul is not nul. Then you can use an alternative between used[t] and notUsed[t]. With this model, you create a number of additional intervals and constraints/expressions that "only" depends on the size of the horizon h and not on the number of tasks n.

But again, the best way would be to avoid enumerating the horizon.

Philippe


#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[dgravot@noos.fr said:]

Thanks Philippe for the advices,

There are indeed side constraints in the "holes" , that is at every time slot where no task is scheduled, there is some "productivity" and one is interested to maximize the productivity over the holes, while maintaining a feasible schedule for the tasks. This is a quite original objective function but I'll certainly appreciate to discuss details about it offline.

Regards
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[phlab said:]

Optional interval variables can be used to capture the intervals of times during which at least one task is executed and intervals of time during which no task executes.

Given a set of tasks represented as interval variables A[i in 1..n], a chain of intervals W[j] that exactly cover the set of points where at least one task A executes can be defined as follows:


1.  int n=...;
2.  dvar interval A[i in 1..n] ...;
3.  cumulFunction CA = sum(i in 1..n) pulse(A[i],1);
4.  dvar interval W[i in 1..n] optional in 1..horizon; // Some work being done by some A[j]
5.  cumulFunction CW = sum(i in 1..n) pulse(W[i],1);
6.  constraints {
7.    forall(i in 1..n-1) {
8.      endBeforeStart(W[i],W[i+1],1);
9.      presenceOf(W[i+1]) => presenceOf(W[i]);
10.  }
11.  forall(i in 1..n) {
12.    alwaysIn(CA, W[i], 1, n);
13.    alwaysIn(CW, A[i], 1, n);
14.  }
15. };


Rationale:
Line 3: the cumul function CA counts the number of tasks A executing at any time t
Lines 4 and 7..10: W[i in 1..n] is a chain of optional intervals (to break symmetries, only the first k intervals will be present, indirectly, k is a decision variable of the problem).
Line 4: the minimal size of 1 for intervals W (when they are present) also allows breaking some symmetries: if an interval W is present, it must represent a non null interval of time where some task execute
Line 8: the minimal delay of 1 in the chain ensure that a block of tasks executing without interruption will be covered by exactly one interval W
Line 5: the cumul function CW counts the number of intervals W executing at any time t (it can be either 0 or 1 as the intervals form a chain)
Line 12: during the execution of a present interval W there must be at least one task A executed (that is: 1<=CA<=n)<br />Line 13: during the execution of a task A there must be at least one interval W present (that is: 1<=CW<=n)<br />
One can easily extend this model to also explicit the intervals of time during which no task executes by using an interval in between the intervals W:


1.  int n=...;
2.  dvar interval A[i in 1..n] ...;
3.  cumulFunction CA = sum(i in 1..n) pulse(A[i],1);
4.  dvar interval W[i in 1..n]  optional in 1..horizon; // Work
5.  dvar interval M[i in 1..n-1] optional in 1..horizon; // Maintenance
6.  cumulFunction CW = sum(i in 1..n) pulse(W[i],1);
7.  constraints {
8.    forall(i in 1..n-1) {
9.      endAtStart(W[i],M[i]);
10.    endAtStart(M[i],W[i+1]);
11.    presenceOf(M[i])  => presenceOf(W[i]);
12.    presenceOf(W[i+1]) => presenceOf(M[i]);
13.  }
14.  forall(i in 1..n) {
15.    alwaysIn(CA, W[i], 1, n);
16.    alwaysIn(CW, A[i], 1, n);
17.  }
18. };


Using these interval variables W and M you can avoid explicitly enumerating time.

Here is a small example that specifies that one cannot work more than 10 units without a maintenance period that will last 10 units. In this pedagogical example, tasks A[i in 1..n] are supposed to have a processing time i and to require (n+1-i) units of a cumulative resource of capacity n.


using CP;
int n=10;
dvar interval A[i in 1..n] size i;
cumulFunction Res = sum(i in 1..n) pulse(A[i], n+1-i); // Constraints on activities
cumulFunction CA = sum(i in 1..n) pulse(A[i],1);
dvar interval W[i in 1..n]  optional size 1..10; // Work
dvar interval M[i in 1..n-1] optional size 10;    // Maintenance
cumulFunction CW = sum(i in 1..n) pulse(W[i],1);
minimize max(i in 1..n) endOf(A[i]);
constraints {
forall(i in 1..n-1) {
  endAtStart(W[i],M[i]);
  endAtStart(M[i],W[i+1]);
  presenceOf(M[i])  => presenceOf(W[i]);
  presenceOf(W[i+1]) => presenceOf(M[i]);
}
forall(i in 1..n) {
  alwaysIn(CA, W[i], 1, n);
  alwaysIn(CW, A[i], 1, n);
}
Res <= n;<br />};





#DecisionOptimization
#OPLusingCPOptimizer