Topic
  • 5 replies
  • Latest Post - ‏2018-03-12T20:23:23Z by AlexFleischer
qtbgo
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.

 

thanks i n advance.

 

  • PhilippeLaborie
    PhilippeLaborie
    117 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
    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
    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
    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
    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
    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 

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

    regards