Hi, I want to generate a, say 10x10, transition matrix including transition times. The transition time is uniformly distributed on e.g. [10, 100] and satisfies triangular inequality.
I wonder how to generate it.
thanks i n advance.
Hi, I want to generate a, say 10x10, transition matrix including transition times. The transition time is uniformly distributed on e.g. [10, 100] and satisfies triangular inequality.
I wonder how to generate it.
thanks i n advance.
- qtbgo
- 2014-03-11T12:50:33Z
Thank you Philippe, is it possible to generate a symmetric matrix satisfying triangular inequality?
Well, you can just symmetrize your matrix before running the Floyd-Warshall algorithm. Note that there was a small typo in my previous code (j<n should read j<=n).
int n=10; int TTMin = 10; int TTMax = 100; int Matrix[i in 1..n][j in 1..n] = (i<=j)?0:TTMin+rand(TTMax-TTMin+1); execute { // Symmetrize for (i=1; i<=n; i++) { for (j=i+1; j<=n; j++) { Matrix[i][j]=Matrix[j][i]; } } // Enforce triangular inequality with Floyd-Warshall algorithm for (k=1; k<=n; k++) { for (i=1; i<=n; i++) { if (i!=k) { for (j=1; j<=n; j++) { if ((j!=k)&&(j!=i)) { if (Matrix[i][k]+Matrix[k][j] < Matrix[i][j]) { Matrix[i][j] = Matrix[i][k]+Matrix[k][j]; } } } } } } }
Philippe
Hello,
The triangular inequality property implies some dependency between the different values in the matrix so I don't think it is possible to ensure that each coefficient in the matrix is uniformly distributed over an interval of integers [TTMin,TTMax]. But if you can slightly relax the shape of the probability distribution, one thing you can easily do is to first generate a matrix with coefficients uniformly distributed in [TTMin,TTMax] and then, apply a Floyd-Warshall algorithm to decrease some coefficients in order to satisfy the triangle inequality. See the OPL code below (note that in the code I additionally assumed a 0 self-distance Matrix[i][i]). As said, in the end the coefficients won't be uniformly distributed (the probability distribution should be some non-increasing function) but maybe it is enough for what you want to do.
int n=10; int TTMin = 10; int TTMax = 100; int Matrix[i in 1..n][j in 1..n] = (i==j)?0:TTMin+rand(TTMax-TTMin+1); execute { // Enforce triangular inequality with Floyd-Warshall algorithm for (k=1; k<=n; k++) { for (i=1; i<=n; i++) { if (i!=k) { for (j=1; j<n; j++) { if ((j!=k)&&(j!=i)) { if (Matrix[i][k]+Matrix[k][j] < Matrix[i][j]) { Matrix[i][j] = Matrix[i][k]+Matrix[k][j]; } } } } } } }
Philippe
- PhilippeLaborie
- 2014-03-11T08:40:30Z
Hello,
The triangular inequality property implies some dependency between the different values in the matrix so I don't think it is possible to ensure that each coefficient in the matrix is uniformly distributed over an interval of integers [TTMin,TTMax]. But if you can slightly relax the shape of the probability distribution, one thing you can easily do is to first generate a matrix with coefficients uniformly distributed in [TTMin,TTMax] and then, apply a Floyd-Warshall algorithm to decrease some coefficients in order to satisfy the triangle inequality. See the OPL code below (note that in the code I additionally assumed a 0 self-distance Matrix[i][i]). As said, in the end the coefficients won't be uniformly distributed (the probability distribution should be some non-increasing function) but maybe it is enough for what you want to do.
<pre class="html dw" data-editor-lang="js" data-pbcklang="html" dir="ltr">int n=10; int TTMin = 10; int TTMax = 100; int Matrix[i in 1..n][j in 1..n] = (i==j)?0:TTMin+rand(TTMax-TTMin+1); execute { // Enforce triangular inequality with Floyd-Warshall algorithm for (k=1; k<=n; k++) { for (i=1; i<=n; i++) { if (i!=k) { for (j=1; j<n; j++) { if ((j!=k)&&(j!=i)) { if (Matrix[i][k]+Matrix[k][j] < Matrix[i][j]) { Matrix[i][j] = Matrix[i][k]+Matrix[k][j]; } } } } } } } </pre>Philippe
Thank you Philippe, is it possible to generate a symmetric matrix satisfying triangular inequality?
- qtbgo
- 2014-03-11T12:50:33Z
Thank you Philippe, is it possible to generate a symmetric matrix satisfying triangular inequality?
Well, you can just symmetrize your matrix before running the Floyd-Warshall algorithm. Note that there was a small typo in my previous code (j<n should read j<=n).
int n=10; int TTMin = 10; int TTMax = 100; int Matrix[i in 1..n][j in 1..n] = (i<=j)?0:TTMin+rand(TTMax-TTMin+1); execute { // Symmetrize for (i=1; i<=n; i++) { for (j=i+1; j<=n; j++) { Matrix[i][j]=Matrix[j][i]; } } // Enforce triangular inequality with Floyd-Warshall algorithm for (k=1; k<=n; k++) { for (i=1; i<=n; i++) { if (i!=k) { for (j=1; j<=n; j++) { if ((j!=k)&&(j!=i)) { if (Matrix[i][k]+Matrix[k][j] < Matrix[i][j]) { Matrix[i][j] = Matrix[i][k]+Matrix[k][j]; } } } } } } }
Philippe