Topic
  • 3 replies
  • Latest Post - ‏2014-03-11T14:05:42Z by PhilippeLaborie
qtbgo
qtbgo
131 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.

 

thanks i n advance.

 

  • PhilippeLaborie
    PhilippeLaborie
    68 Posts
    ACCEPTED ANSWER

    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
    PhilippeLaborie
    68 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
    qtbgo
    131 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
    PhilippeLaborie
    68 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