Topic
2 replies Latest Post - ‏2013-12-08T04:09:40Z by JorisK
JorisK
JorisK
18 Posts
ACCEPTED ANSWER

Pinned topic CP TSP model

‏2013-11-27T05:23:34Z |

Hi,

I'm having some trouble with my c++ CP model. In my objective I would like to do the following:

min sum_i distanceMatrix[ x_i ][ x_{i+1} ][ i ]

Here, x_i is a variable indicating the city I visit at time i and distanceMatrix is a 3 dimensional int array.

Here is part of my implementation:

==================

IloModel model(env);
 
//Define constants
// create travel cost matrix
IloIntArray3 distanceMatrix(env,tdTSP->nrVertices);
for( unsigned int i = 0; i < tdTSP->nrVertices; i++ ) {
distanceMatrix[i]=IloIntArray2(env,tdTSP->nrVertices);
for( unsigned int j = 0; j < tdTSP->nrVertices; j++ ) {
distanceMatrix[i][j]=IloIntArray(env,tdTSP->nrVertices);
for( unsigned int t = 0; t < tdTSP->nrVertices; t++ ) {
distanceMatrix[i][j][t]=tdTSP->getDistance(i,j,t);
}
}
}
 
 
//Define variables
 
   IloIntVarArray visitAt = IloIntVarArray(env, tdTSP->nrVertices, 0, tdTSP->nrVertices-1);
   for(int i=0; i<tdTSP->nrVertices; i++){
    visitAt[i].setName("Vertex: "+i);
   }
 
 
   //Define objective
   IloIntVar obj_var= IloIntVar(env, 0, INF, "obj");
   model.add( IloMinimize(env, obj_var) );
   IloIntExpr obj(env);
   for(int i=0; i<tdTSP->nrVertices-1; i++){
    obj += distanceMatrix[visitAt[i]][visitAt[i+1]][i];
   }
model.add( obj_var == obj);
 

=================

 

The problem is that   obj += distanceMatrix[visitAt[i]][visitAt[i+1]][i]; is not allowed. The compiler says: "no match for operator[]". Any suggestions on how to fix this?

Updated on 2013-11-27T05:31:15Z at 2013-11-27T05:31:15Z by JorisK
  • PhilippeLaborie
    PhilippeLaborie
    42 Posts
    ACCEPTED ANSWER

    Re: CP TSP model

    ‏2013-11-27T09:16:52Z  in response to JorisK

    Hello,

    There is indeed no such a multi-dimensional expression in the C++ API of CP Optimizer. You will need to flatten your 3D matrix "distanceMatrix" into a 1D array and index it with an expression computed from the 3 arguments that access the 3D matrix.

    Philippe

    • JorisK
      JorisK
      18 Posts
      ACCEPTED ANSWER

      Re: CP TSP model

      ‏2013-12-08T04:09:40Z  in response to PhilippeLaborie

      Thank you. I was able to solve the problem with your suggestion. For future reference, here is (part)  of my implementation:

       

      const int N=tdTSP->nrVertices+1;
      const int N2=N*N;
      const int N3=N2*N;
       
      //Create a flat distance matrix.
      IloIntArray  flatDistanceArray(env, N3); //travel distance from (i,j,t)=i*n+j*n+t
      for(int i=0; i<N3; i++)
      flatDistanceArray[i]=0;
       
      for(int j=1; j<tdTSP->nrVertices; j++){
      flatDistanceArray[j]=tdTSP->getDistance(0,j,0);
      }
       
      for(int i=1; i<tdTSP->nrVertices; i++){
      for(int j=1; j<tdTSP->nrVertices; j++){
      if(i==j)
      continue;
      for(int t=1; t<tdTSP->nrVertices-1; t++){
      flatDistanceArray[t*N2+i*N+j]=tdTSP->getDistance(i,j,t);
      }
      }
      }
       
      for(int i=1; i<tdTSP->nrVertices; i++){
      int j=tdTSP->nrVertices;
      int t=tdTSP->nrVertices-1;
      flatDistanceArray[t*N2+i*N+j]=tdTSP->getDistance(i,j,t);
      }
       
      //Define variables
       
      visitAt = IloIntVarArray(env, tdTSP->nrVertices+1, 1, tdTSP->nrVertices-1);
      indexAt = IloIntVarArray(env, tdTSP->nrVertices, 0, N3);
       
      //Define objective
      IloIntVar obj_var= IloIntVar(env, 0, INF, "obj");
      model.add( IloMinimize(env, obj_var) );
      IloIntExpr obj(env);
      for(int i=0; i<tdTSP->nrVertices; i++){
      obj += flatDistanceArray[indexAt[i]];
      }
      model.add( obj_var == obj);
       
       
      //Define constraints.
       
      //1. Link visitAt and indexAt variables
      for(int i=0; i<tdTSP->nrVertices; i++){
      model.add(indexAt[i]==N2*i+visitAt[i]*N+visitAt[i+1]);

       

      }

      Some side notes:

      1. The flat data structure is quite cumbersome to maintain. It would be nice if a future release of CP Optimizer would support n-dimensional element constraints; flattening a matrix can be automated behind the scenes.

      2. This model has an extremely large memory consumption. My guess would be that this is due to the internal representation of the element constraints.