Originally posted by: davidoff

Hello

I wonder if there is an efficient way to forbid some given transitions within a sequence of non-overlapping intervals. Let's say I have a sequence of non-overlapping interval among an array of intervals itvs and I would like to add a constraint saying that for instance itvs[1] cannot be followed by itvs[2]. What I do in the sample below is to use the typeOfNext type of each interval and then explicitely writes typeOfNext(1) must be different than T[2] in order to forbid this transition.

Is that an efficient model ? As there is a prev operator for a sequence , I was wondering if there is something like "nonprev" that would be more efficient

Thanks

David

using CP; range horizon = 0..10; range r = 1..3; dvar interval itvs[r] in horizon size 1; dvar interval a = itvs[1]; 

int T[i in r] = i; dvar sequence route in itvs types T;   

int dist[i in r][j in r] = ftoi(abs(i-j)); tuple triplet 
{ 

int c1; 

int c2; 

int d; 
}; 
{triplet
} Dist = 
{ <i, j, dist[i,j]> | i in r, j in r
};   dexpr 

int tynext[i in r] = typeOfNext(route,itvs[i],T[i],T[i]);   tuple Edge 
//itvs[i1]->itvs[i2] will be forbidden 
{ 

int i1;
//index of the origin 

int i2; 
//index or the tail  
} 
{Edge
} forbidTransition = 
{<1,2>
};
//forbid itvs1 to be followed by itvs2 subject to 
{ noOverlap(route,Dist); first(route,a); 
//last(route,c); forall(<i1,i2> in forbidTransition) tynext[i1] != T[i2]; 
} execute
{writeln(route);
}

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello,
The model using previous or next expressions should be more or less equivalent.
An alternative model would be to use very large transition time for incompatible transitions. For that, you need to specify that the transition time need to hold between immediate successors in the sequence. In your model, that would be something like:

tuple Edge 
{ 

int i1; 
//index of the origin 

int i2; 
//index or the tail  
} 
{Edge
} forbidTransition = 
{<1,2>
}; 

int largeTT = 1000000; 

int dist[i in r][j in r] = (<i,j> in forbidTransition ? largeTT : ftoi(abs(i-j)));

And then the declaration of the noOverlap constraint:

noOverlap(route,Dist,1); 
// Transition time holds between immediate successors

The advantage, especially if the model is large, is that the engine does not need to maintain the next (or previous) expressions.

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: davidoff

Thanks Philippe

Actually, this is a model that is run several times during a branch and price scheme where forbidden transitions are linked to some branching in the master model. So far, I regenerate the cp slave model at each iteration, so both approaches (yours and mine) can be implemented

Howeever, I usually speed up iterations between models in OPL, I try to avoid regenerating the models from scratch and use some bounds change (as it is done in the mulprod_change_main.mod model). This works fine for instance to forbid a given interval : I have in the original model some constraints such as forall(v in itvs) presenceOf(itv[v])==active[v] , and to dynamically forbid one interval in the next iteration, I simply do active[v].setUb(0). Then, calling cp.solve() after these modifications

I think I could adapt my model with some initial dummy constraints saying that for each pair of interval i1,i2 then I have
typeOfNext(i1) != Ti2 + dummyi1,i2
I initially set up dummyi1,i2 to a big range http://0..M so that all these constraints will be satisfied, and once again, during my iterations, I can set upper bound of dummyi1,i2 to 0 whenever I want to forbid this transition.

I have not tested yet this way to see if it's better than regenerating the model. For sure, there will be a quadratic number of constraints to forbid transitions, even if a few of them will be actually propagating.

David
#DecisionOptimization
#OPLusingCPOptimizer