Topic
• 5 replies
• Latest Post - ‏2018-03-12T20:23:23Z by AlexFleischer
qtbgo
134 Posts

# Pinned topic how to generate transition time satisfying triangular inequality?

‏2014-03-11T08:08:37Z |

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.

• PhilippeLaborie
117 Posts

#### Re: how to generate transition time satisfying triangular inequality?

‏2014-03-11T14:05:42Z
• 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

• PhilippeLaborie
117 Posts

#### Re: how to generate transition time satisfying triangular inequality?

‏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.

```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

• qtbgo
134 Posts

#### Re: how to generate transition time satisfying triangular inequality?

‏2014-03-11T12:50:33Z

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?

• PhilippeLaborie
117 Posts

#### Re: how to generate transition time satisfying triangular inequality?

‏2014-03-11T14:05:42Z
• 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

• AndyHam
50 Posts

#### Re: how to generate transition time satisfying triangular inequality?

‏2018-03-12T18:24:25Z

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).

<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 { // 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]; } } } } } } } </pre>

Philippe

This is great! I am trying to use this code to generate the traveling distance. Every time I run the code, it generates the same matrix. If we need to generate 10 different matrices, how can make it happen (or how to introduce "random seed")?

• AlexFleischer
255 Posts

#### Re: how to generate transition time satisfying triangular inequality?

‏2018-03-12T20:23:23Z
• AndyHam
• ‏2018-03-12T18:24:25Z

This is great! I am trying to use this code to generate the traveling distance. Every time I run the code, it generates the same matrix. If we need to generate 10 different matrices, how can make it happen (or how to introduce "random seed")?

Hi

you should have a look at srand

regards