Originally posted by: davidoff

In the following sample, I have three activities in a non-overlapping sequence.
These 3 activities are optional but I would like to enforce the total ordering

Unfortunately, I'm afraid this can't be done using only prev , as shown in the following sample

using CP;   dvar interval A[i in 1..3] optional size 1; dvar sequence s in A;   constraints 
{ noOverlap(s); prev(s,A[1],A[2]); prev(s,A[2],A[3]); 
//before(s, A[1],A[3]);//mandatory otherwise the next constraint is valid ! prev(s,A[3],A[1]);  
//valid ! 
//endBeforeStart(A[1],A[2]); 
//endBeforeStart(A[2],A[3]); 
} 
}

Generally speaking, it seems that if I want to order totally n optional intervals A1,...,An in a non overlapping sequence, I must add a quadratic number of constraints

forall(i in 1..3, j in 1..3 : i<j) before(s,A[i],A[j]);

Is there a better way to enforce a total ordering ? I think using artificial transition times is a good workaround :

using CP;   tuple Transition
{ 

int i1; 

int i2; 

int d; 
} 

int M = 100;
// 
{Transition
} Dist = 
{ <1,1,0> , <1,2,0>,<1,3,0>,<2,1,M>,<2,2,0>,<2,3,0>,<3,1,M>,<3,2,M>,<3,3,0>
}; dvar interval A[i in 1..3] optional(i ==2) in 0..10 size 1  ; dvar sequence s in A types all(i in 1..3) i;   constraints 
{ noOverlap(s , Dist, 1); prev(s,A[1],A[2]); prev(s,A[2],A[3]); 
//before(s, A[1],A[3]); prev(s,A[3],A[1]); 
//endBeforeStart(A[1],A[2]); 
//endBeforeStart(A[2],A[3]); 
//forall(i in 1..3, j in 1..3 : i<j) 
//before(s,A[i],A[j]); 
}

Is there any other (better) way ?

Thanks

David
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi David

If I understand well, you want to map a known chain of intervals but presence is unknown on a chain of present interval enforcing the same order.

The initial chain of interval is in non overlap. That is you have start after end constraints.

To achieve that I would suggest to create a chain of fake interval: here the model I suggest

range Opers 1..n-1;
int PtsOpers=...;

dvar interval opersi in Opers optional size Pts[i];
dvar interval startsOpers size 0;
dvar interval endsOpers size 0;

subject to {
forall(i in Opers];
startAtStart[starts[i], opers[i]);
endAtEnd(ends[i], opers[i]);
endBeforeStart(starts[i], end[i]);
if (i != 0) {
endBeforeStart(endsi-1, starts[i]); // here the endBeforeStart constraint between opers
}
}

That is I map the start points and the end points of operation to instantaneous events
that I constraint to make a chain formally enforcing the noOverlap.
As you can see it is easy to implement other chains than noOverlap one or having delay between operations.
The fact that starts and ends intervals has no duration make they do not consumes duration on the time axis.

I suggest anyway to solve the problem with a search phase that exclude starts and end intervals so that the fixing of theyr date does not implies prematurely having operations absnet.

Hope that helps
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: davidoff

Thanks for the trick . Simple but clever !

Generally speaking, when you already know precedence order, do you think it is redundant / costly / efficient / useless to add a non overlap constraint ?

Now , more specifically in my project, I know the order between tasks, each task is associated to a given site among a certain number of possible sites and I know the distance (in time units) between two sites.

For instance, I can have a storage (task S) in sites S1,S2 , followed by an other task F (let's say filling a tank) that can also be done in plant P1 or P2, and then other tasks. Several routes are possible so usually , all tasks are optional.

Given a transportation matrix M between any site, I'd like to model the transportation time T between two consecutive tasks. Using a non overlap constraint for the sequence of S1,S2,P1,P2 is interesting but it only models a minimum transition time between two consecutive activities. The only way I can see is to add all constraints pairs such as

P1.startAtEnd(S1, M[P1.site,S1.site] ) P1.startAtEnd(S2, M[P1.site,S2.site] ) P2.startAtEnd(S1, M[P2.site,S1.site] ) P2.startAtEnd(S1, M[P2.site,S2.site] )

This is much more "verbose" than a single no-overlap constraint based on all the possible sub activities with their type as the corresponding location (site).

Is there a way to define a non-overlap with an exact transition time between tasks (and not only a minimal transition time) ?
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello David.

For your first question, about adding noOverlap constraint if the precedence order is know. If the ordering of the interval is completely known (you have a chain) then it is more effective to replace noOverlap by precedences. The noOverlap constraint is then useless, it will not improve propagation and it will only slow the engine down.

If I understand you right, in your problem, you know that task S is before task F. However task S has two alternatives (S1 and S2), F has also two alternatives (P1 and P2) and delay between S and F depends on the chosen alternatives. And additionally, you want to ensure that this delay is exact.

There is no variant of noOverlap constraint which would interpret transition times and exact times instead of minimum times. However, by default CP Optimizer tries to schedule every task as soon as possible. Therefore the delay between S and F in the solution will be prolonged only if (a) there's another constraint which does not allow to schedule F sooner or (b) it improves objective value to schedule F later. If neither (a) nor (b) is your case, then you don't have to add the constraint.

Otherwise yes, first solution is to add a quadratic number of startAtEnd constraints for every combination of Si and Pi as you suggest in your post. In this case it will probably help to also add a redundant precedence between masters of the alternatives S and F using minimum and maximum allowed delay:

endBeforeStart(F, S, minDelay); startBeforeEnd(F, S, -maxDelay);

Second solution is to use endsAtStart precedences with delay given by expression. In this expression you can evaluate the exact value of the delay using presenceOf expressions. I suggest to use lookup into constant integer array (we call it element constraint) because it will propagate better than complex expression. In the case of S and F we can have two-dimensional array DistSF with four values. Then we can write:

endAtStart(S, F, DistSF[presenceOf(S1)][presenceOf(P1)]);

If there are more than 2 alternatives (like S1, S2 and S3 for S) then you can use more complicated expressions as index into array DistSF. Or, you can create integer variable SAlt and use it for element constraint:

dvar 

int SAlt in 0..3; ... (SAlt == 0) == presenceOf(S1); (SAlt == 1) == presenceOf(S2); (SAlt == 2) == presenceOf(S3);

This code with integer variable will probably propagate better than complex expressions.

For maximum propagation, you can even combine both approaches together (i.e. quadratic number of precedences between alternatives + precedences with delay expressions for master intervals). I suggest you to do some experiments which approach works best for you.

I also want to return to the solution suggested above with "fake" intervals called "starts" and "ends". I think you don't need both "starts" and "ends". Having only "starts" or only "ends" should be enough. Also, synchronization between "fake" and "real" intervals should be done on masters of alternative. For example, assuming S is k-th interval in the sequence, it is better to do:

startAtStart(S, starts[k]);

instead of:

startAtStart(S1, starts[k]); startAtStart(S2, starts[k]);

I hope it helps, Petr
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: davidoff

Using starts and ends fake intervals, I'm not clear how you are able to enforce the distance between two actual consecutive tasks.
In the following sample, I just add the delay between two consecutive tasks

int n; range Opers = 0..n-1; 

int Pts[Opers]=...; 

int delay = ...;
//a constant delay between two consecutive real operations   dvar interval opers[i in Opers] optional size Pts[i]; dvar interval starts[Opers] size 0; dvar interval ends[Opers] size 0;   subject to 
{ forall(i in Opers)
{ startAtStart(starts[i], opers[i]); endAtEnd(ends[i], opers[i]); endBeforeStart(starts[i], ends[i]); 

if (i != 0) endBeforeStart(ends[i-1], starts[i]); 
// here the endBeforeStart constraint between opers startAtEnd(opers[i-1],opers[i],delay);
//NEW delay between two consecutive operations 
} 
}

Now, if only operations 0 and 2 are chosen, 0 and 2 should be distant of "delay" units of time. But this won't be enforced in the model cause none of the three following constraints will be active when opers[1] is unactive

startAtEnd(opers[i-1],opers[i],delay);

And it would be false to change the constraints between ends and starts with something like

startAtEnd(ends[i-1],starts[i],delay);

since in this case, I would have 1 and 3 distant of "2*delay" units of time while it should be only "delay" units.
Did I miss something here ?
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello David.

You're right, precedences:

startAtEnd(opers[i-1],opers[i],delay);

will not work.

You may also try to constraint startOfNext using typeOfNext the following way. Create dummy non-optional interval variable dummyLast and sequence variable (called seq in the following code) using all tasks and also interval dummyLast. Interval dummyLast will be the last one on the sequence:

last(seq, dummyLast);

Assign types to all intervals on the sequence, however keep type 0 reserved only for dummyLast. We will also need integer array distFromX, which tells you for every type how long is transition time from interval X to that type. Value of distFromX for type 0 should be 0. Now, we can constraint every interval X on the sequence the following way:

startOfNext(seq, X, 0) = endOf(X, 0) + distFromX[typeOfNext(seq, X, 0)];

Note that if X will be absent then startOfNext, endOf and typeOfNext return also zeros. Value of distFromX for 0 is 0 and therefore the constraint is reduced to 0=0. There is dummyLast at the end of the sequence so we don't have to take care about the case when X is last.

I hope it helps, Petr
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: davidoff

Here is a sample related to your idea. You're right now : the distance will be properly taken into account between any operation and its actual successor.

int n=3; range Opers = 1..n; 

int Pts[i in Opers]=1; 

int delay = 2;
//a constant delay between two consecutive real operations   

int distFrom[i in Opers,j in 0..n] = j==0?0:delay;   dvar interval opers[i in Opers] optional in 0..10 size Pts[i]; dvar interval dummy size 0; dvar sequence seq in append(opers,dummy)  types append(all(i in Opers) i,0);   constraints
{ presenceOf(opers[1])==1; presenceOf(opers[3])==1; presenceOf(opers[2])==0; prev(seq , opers[3] ,opers[1]); 
//still a solution with this constraint last(seq,dummy); forall(i in Opers)
{ startOfNext(seq, opers[i] , 0) == endOf(opers[i], 0) + distFrom[i, typeOfNext(seq,opers[i],0)]; 
} 
}

However, this does not guarantee that the order will be correct (e.g opers[i] will be before opers[j] whenever both operations are active and i<j). As I said before, this could be achieved at the cost of a non-overlap constraint with high transition times for unvalid orders or at the cost of a quadratic number of "before" constraints on the sequence. But maybe you still have an other better idea ?

int n=3; range Opers = 1..n; 

int Pts[i in Opers]=1; 

int delay = 2;
//a constant delay between two consecutive real operations   

int distFrom[i in Opers,j in 0..n] = j==0?0:delay; tuple Transition 
{ 

int type1; 

int type2; 

int d; 
} 

int M=100;
//impossible transitions will be set to this value 
{Transition
} transitions = 
{ <i,j,((j<i && j>0)?M:distFrom[i,j])> | i in Opers, j in 0..n               
};   dvar interval opers[i in Opers] optional in 0..10 size Pts[i]; dvar interval dummy size 0; dvar sequence seq in append(opers,dummy)  types append(all(i in Opers) i,0);   constraints
{ presenceOf(opers[1])==1; presenceOf(opers[3])==1; presenceOf(opers[2])==0; 
//prev(seq , opers[3] ,opers[1]);//no solution with one of the two next constraint  forall(ordered i,j in Opers) before(seq , opers[i] ,opers[j]); noOverlap(seq , transitions); last(seq,dummy); forall(i in Opers)
{ startOfNext(seq, opers[i] , 0) == endOf(opers[i], 0) + distFrom[i, typeOfNext(seq,opers[i],0)]; 
} 
}

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

The idea was to combine two approaches together: dummy intervals "starts" and/or "ends" for enforcing the right order of intervals and startOfNext to enforce the exact transition times.

Petr
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: davidoff

Yes, you're right. That sounds better indeed than the non-overlap or the before constraints.
Here is the last code with your two ideas

Thank you very much for all your advices.

David

int n=3; range Opers = 1..n; 

int Pts[i in Opers]=1; 

int delay = 2;
//a constant delay between two consecutive real operations   

int distFrom[i in Opers,j in 0..n] = j==0?0:delay;   dvar interval opers[i in Opers] optional in 0..10 size Pts[i]; dvar interval dummy size 0; dvar sequence seq in append(opers,dummy)  types append(all(i in Opers) i,0);   dvar interval starts[Opers] size 0; dvar interval ends[Opers] size 0;     constraints
{ presenceOf(opers[1])==1; presenceOf(opers[3])==1; presenceOf(opers[2])==0; 
//prev(seq , opers[3] ,opers[1]);//no solution with the following block  forall(i in Opers)
{ startAtStart(starts[i], opers[i]); endAtEnd(ends[i], opers[i]); endBeforeStart(starts[i], ends[i]); 

if (i > 1) endBeforeStart(ends[i-1], starts[i]); 
// here the endBeforeStart constraint between opers 
} last(seq,dummy); forall(i in Opers)
{ startOfNext(seq, opers[i] , 0) == endOf(opers[i], 0) + distFrom[i, typeOfNext(seq,opers[i],0)]; 
} 
}

#DecisionOptimization
#OPLusingCPOptimizer