Originally posted by: qtbgo

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.

Originally posted by: PhilippeLaborie

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

Originally posted by: qtbgo

Thank you Philippe, is it possible to generate a symmetric matrix satisfying triangular inequality?

Originally posted by: PhilippeLaborie

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

Originally posted by: AndyHam

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 

https://www.ibm.com/support/knowledgecenter/SSSA5P_12.5.0/ilog.odms.ide.help/OPL_Studio/opllang_quickref/topics/tlr_oplf_srand.html

regards