Originally posted by: davidoff

I want to calculate the distance between two consecutive trips of a sequence

The expression that I know for that is to compute a matrix between all types of the intervals and given this matrix M[type1,type2] , I can compute the interval between any interval i of type ti and its successor through M[  ti, typeOfNext(i) ]. This works well with optional intervals too

Now, I'm wondering how we can achieve some kind of sparsity in the matrix M. Indeed, i may have a few successors only, so could we take advantage of this in order to compute only a sparse matrix instead of pre-compute the matrix of all types. Since I use primary keys of the intervals as types, this leads indeed to a huge matrix if I want to store all these infos .

In a nutshell, does M absolutely need to be dense, storing all the relations between types whereas the actual possible relations are much less ?

thanks

David

Originally posted by: PhilippeLaborie

Hello,

There are two types of "matrices" in your question.

1. CP Optimizer uses the notion of a transition distance as a built-in structure to represent sequence dependent transition distances. This structure is an instance of class IloTransitionDistance in the APIs or a set of triples in OPL. The structure is used in the constraint noOverlap. This structure is not sparse so it will be in O(n^2) in memory if you have n different types in the sequence variable. You can save memory on this structure in two ways: (1) merge types that behave in the same way with respect to setup distances and (2) you can post several noOverlap(seqi,Mi) with different transition distances Mi on several sequence variables seqi that associate different types to the same interval variables. The second idea can help in cases you have transition distances of different nature in the problem. The conjunction of noOverlap constraint will propagate the "max" of the transition distances of the different matrices Mi and you can use the first idea to use less types in each noOverlap.

2. If the transition time or cost is modeled thanks to expressions like typeOfNext, you are not using the notion of transition distance any more, but, instead, some classical expressions/constraints on integer expressions. For instance Ai[typeOfNext(i)] where Ai is an array of integer. In general indeed, Ai can be a row of matrix M but you can use any combination of integer constraint/expression so be more compact depending on your problem. For instance if your matrix is very sparse, you could use some table constraint on the tuples <typeOfNext(i), transition value from i to typeOfNext(i)> (see constraint allowedAssignments).

Philippe

Originally posted by: davidoff

Thanks Philippe,

Using less types is difficult for me since the transition represents precedence between two trips. Actually, these trips have fixed dates so I'm wondering if a noOverlap constraint is usefull or not when it comes to performances. But it certainly helps to model the problem thanks to the typeOfNext feature that allows me to compute easily distances, especially with the allowedAssignments that you suggested

David