Originally posted by: max__x

in 
OPL model and script for Symmetric Travelling Salesman Problem, there is code:

tuple 
Subtour { 
int 
size; 
int 
subtour[Cities]; }
{Subtour} subtours = ...;

 

but after I input the code, it says not defined subtours, can any one tell me how to define it.

Is that means I need to define the subtours in the data, file ?

Many thanks.

 

‹

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi

you should have a look at the example in

CPLEX_Studio1261\opl\examples\opl\models\TravelingSalesmanProblem

regards

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: max__x

Dear AlexFleischer, I cannot find the example you give, since the website of the attached cannot be found.

can you tell me directly ?

Actually I want to solved when n=10, and all the distance between each pair of cities has been defined: distance[i][j]. The problem of this code is said the subtour is not defined, can you tell me how to define it??

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi

CPLEX_Studio1261\opl\examples\opl\models\TravelingSalesmanProblem is not a web link but a folder in the CPLEX product.

To make your example work if the only error is about subtours then in the .dat you may write

subtours={};

regards

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: max__x

Yes, it was just the error of subtours, and the I was wrong to write the format of subtours. And now I have fixed it.

Another question is when the city number get larger, there are so many suboturs need to define, do you know any convenient way to define subours? Because, when the city number is 10, there are so many subtours in this case.

thank you

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Then you may try with CPO : see https://www.ibm.com/developerworks/community/forums/html/topic?id=5efb1db1-c642-4877-af60-b330f959a534&ps=25

regards

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Ashraf_ISE

Hello there Alex,

I have a question if you don't mind me asking. I'm fairly new to Cplex but I have taken number of weeks going over the TSP example and your CPO one as well. Now I'm a little comfortable asking this question. 

I have a number m, and after the sales man visits a node, the mth visit after that should be within a specific distance d from that first node. d and m are fixed. SO if m = 4, then the salesman visit any 5 nodes at first, then the 6 visited node should be within d from the node visited first, the 7th visited should be d distance from the 2nd visited, the 8th is near the 3rd,..... , the 1th. near the 6th. and so on. 

 

For the example here I couldn't find a way to get the sequence so I formulate that constraint. For CPO example, there is a sequence variable, but I couldn't find a way to add the constraint to the length between intervals that are m intervals apart.

 

I hope you can give some some insight on how to formulate a sequence variable, and use it in my constraints.

Sorry for bugging you with this

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

let me give you a small example to start with.

Let me change https://www.ibm.com/developerworks/community/forums/html/topic?id=5efb1db1-c642-4877-af60-b330f959a534 to show you

Suppose d=300 and m=3 then you could turn the .mod into

using CP;
int     n       = ...;
range   Cities  = 1..n;

int realCity[i in 1..n+1]=(i<=n)?i:1;

 

// Edges -- sparse set
tuple       edge        {int i; int j;}
setof(edge) Edges       = {<i,j> | ordered i,j in 1..n};
setof(edge) Edges2       = {<i,j> | i,j in 1..n+1};  // node n+1 is node 1

int         dist[Edges] = ...;
int         dist2[<i,j> in Edges2]=(realCity[i]==realCity[j])?0:
((realCity[i]<realCity[j])?dist[<realCity[i],realCity[j]>]:dist[<realCity[j],realCity[i]>]);

int dist2b[i in Cities,j in Cities]=dist2[<i,j>];

dvar interval itvs[1..n+1] size 1;

 

 

dvar sequence seq in all(i in 1..n+1) itvs[i];

dvar sequence seq2 in all(i in 1..n+1) itvs[i] types all(i in 1..n+1)i;

// Gives which city is visited after city i
dvar int nextCity[1..n+1] in 1..n+1;

// Power 2
dvar int nextCity2[1..n+1] in 1..n;

// Power 3
dvar int nextCity3[1..n+1] in 1..n;

 

execute
{

cp.param.TimeLimit=60;
var f = cp.factory;
  cp.setSearchPhases(f.searchPhase(seq));
}

tuple triplet { int c1; int c2; int d; };
{triplet} Dist = {
      <i-1,j-1,dist2[<i ,j >]>
           |  i,j in 1..n+1};

          
           
minimize endOf(itvs[n+1]) - (n+1);           
subject to
{
    startOf(itvs[1])==0; // break sym
    noOverlap(seq,Dist,true);    // nooverlap with a distance matrix
    last(seq, itvs[n+1]); // last node
    
    sameSequence(seq,seq2);
    
    forall(i in 1..n+1) nextCity[i]==(typeOfNext(seq2,itvs[i],1)-1) mod n+1 ;
    
    forall(i in 1..n+1) nextCity2[i]==nextCity[nextCity[i]];
    
    forall(i in 1..n+1) nextCity3[i]==nextCity[nextCity2[i]];
    
    
    forall(i in 1..n-1) dist2b[i,nextCity3[i]]<=300;
}
          
          
 int  x[<i,j> in Edges]=prev(seq,itvs[i],itvs[j])+prev(seq,itvs[j],itvs[i]);
 int  isPrevFromNPlus1[i in 1..n]=prev(seq,itvs[i],itvs[n+1]);
 int l=first({i | i in 1..n : isPrevFromNPlus1[i]==1});
 edge el=<1,l>;
 
 execute
 {
 isPrevFromNPlus1;
 x;
 x[el]=1;
 }
 
 // Let us check here that the constraints of the IP model are ok
 assert forall (j in Cities)
        as:sum (<i,j> in Edges) x[<i,j>] + sum (<j,k> in Edges) x[<j,k>] == 2;
        
// Let us compute here the objective the IP way
int cost=sum (<i,j> in Edges) dist[<i,j>]*x[<i,j>];

execute
{
writeln(cost);
}       

and .dat (same as in OPL example)

n = 17;
dist = [
633
257
91
412
150
80
134
259
505
353
324
70
211
268
246
121
390
661
227
488
572
530
555
289
282
638
567
466
420
745
518
228
169
112
196
154
372
262
110
437
191
74
53
472
142
383
120
77
105
175
476
324
240
27
182
239
237
84
267
351
309
338
196
61
421
346
243
199
528
297
63
34
264
360
208
329
83
105
123
364
35
29
232
444
292
297
47
150
207
332
29
249
402
250
314
68
108
165
349
36
495
352
95
189
326
383
202
236
154
578
439
336
240
685
390
435
287
184
140
542
238
254
391
448
157
301
145
202
289
55
57
426
96
483
153
336
];

 

regards

 

https://www.linkedin.com/pulse/puzzles-having-fun-useful-mathematics-alex-fleischer/

 

 

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Ashraf_ISE

Alex,

 

Thank you so much. this is great. I can't stress how much I appreciate it.

I have two more questions if you don't mind, and I'm sorry for bugging you with this.

in your example m = 3, so the solution visits three nodes before it comes back to visit a node in the neighborhood of the current one. That means at the beginning there are four nodes to be visited before this constraint is active- 1st, 2nd, 3rd, 4th, and the 5th one is near the 1st that was visited. What if I wanna fix the indices of these four nodes? how can I set the set this initial fixed solution?

 

also can I change the value of m or d after specific number of iterations? In your example n = 17 and m = 3, can I say after the 9th iteration (9th node in the sequence is found) change m to 4 or d to 350?

 

Thank you again 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

if you want to visit 1 and then 2 and then 4 you may write

nextCity[1]==2;
    nextCity[2]==4;

about your 2nd question, citiesVisited will tell you which city is visited at step i so with that you ll be able to do what you need:

I changed the .mod into

using CP;
int     n       = ...;
range   Cities  = 1..n;

int realCity[i in 1..n+1]=(i<=n)?i:1;

 

// Edges -- sparse set
tuple       edge        {int i; int j;}
setof(edge) Edges       = {<i,j> | ordered i,j in 1..n};
setof(edge) Edges2       = {<i,j> | i,j in 1..n+1};  // node n+1 is node 1

int         dist[Edges] = ...;
int         dist2[<i,j> in Edges2]=(realCity[i]==realCity[j])?0:
((realCity[i]<realCity[j])?dist[<realCity[i],realCity[j]>]:dist[<realCity[j],realCity[i]>]);

int dist2b[i in Cities,j in Cities]=dist2[<i,j>];

dvar interval itvs[1..n+1] size 1;

 

 

dvar sequence seq in all(i in 1..n+1) itvs[i];

dvar sequence seq2 in all(i in 1..n+1) itvs[i] types all(i in 1..n+1)i;

// Gives which city is visited after city i
dvar int nextCity[1..n+1] in 1..n+1;

// Power 2
dvar int nextCity2[1..n+1] in 1..n;

// Power 3
dvar int nextCity3[1..n+1] in 1..n;

// rank in the travel
dvar int citiesRank[1..n] in 1..n*n;

// traveledCities
dvar int citiesVisited[1..n];

execute
{

cp.param.TimeLimit=60;
var f = cp.factory;
  cp.setSearchPhases(f.searchPhase(seq));
}

tuple triplet { int c1; int c2; int d; };
{triplet} Dist = {
      <i-1,j-1,dist2[<i ,j >]>
           |  i,j in 1..n+1};

          
           
minimize endOf(itvs[n+1]) - (n+1);           
subject to
{
    startOf(itvs[1])==0; // break sym
    noOverlap(seq,Dist,true);    // nooverlap with a distance matrix
    last(seq, itvs[n+1]); // last node
    
    sameSequence(seq,seq2);
    
    forall(i in 1..n+1) nextCity[i]==(typeOfNext(seq2,itvs[i],1)-1) mod n+1 ;
    
    forall(i in 1..n+1) nextCity2[i]==nextCity[nextCity[i]];
    
    forall(i in 1..n+1) nextCity3[i]==nextCity[nextCity2[i]];
    
    
    forall(i in 1..n-1) dist2b[i,nextCity3[i]]<=300;
    
    
    
    forall(i in 1..n) (nextCity[i]!=1) => (citiesRank[nextCity[i]]==citiesRank[i]+1);
    forall(i in 1..n) (nextCity[i]==1) => (citiesRank[nextCity[i]]==1);
    
    inverse(citiesRank,citiesVisited);
}
          
          
 int  x[<i,j> in Edges]=prev(seq,itvs[i],itvs[j])+prev(seq,itvs[j],itvs[i]);
 int  isPrevFromNPlus1[i in 1..n]=prev(seq,itvs[i],itvs[n+1]);
 int l=first({i | i in 1..n : isPrevFromNPlus1[i]==1});
 edge el=<1,l>;
 
 execute
 {
 isPrevFromNPlus1;
 x;
 x[el]=1;
 }
 
 // Let us check here that the constraints of the IP model are ok
 assert forall (j in Cities)
        as:sum (<i,j> in Edges) x[<i,j>] + sum (<j,k> in Edges) x[<j,k>] == 2;
        
// Let us compute here the objective the IP way
int cost=sum (<i,j> in Edges) dist[<i,j>]*x[<i,j>];

execute
{
writeln(cost);
}        
       

regards

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Ashraf_ISE

I'm still having problem with the solution I get for my n=64 instance of the TSP. 

I added an extra power to your code

dvar int nextCity4[1..n+1] in 1..n;

 

and also used your previous answer to set the first four cities to visit- 1,8 , 57, 64

     nextCity[1]==8;
    nextCity[8]==57;
    nextCity[57]==64;

so to recap, n = 64, n = 4 and d=3. My distance data is attached below 

 

using CP;
int     n       = ...;
range   Cities  = 1..n;

int realCity[i in 1..n+1]=(i<=n)?i:1;

 

// Edges -- sparse set
tuple       edge        {int i; int j;}
setof(edge) Edges       = {<i,j> | ordered i,j in 1..n};
setof(edge) Edges2       = {<i,j> | i,j in 1..n+1};  // node n+1 is node 1

int         dist[Edges] = ...;
int         dist2[<i,j> in Edges2]=(realCity[i]==realCity[j])?0:
((realCity[i]<realCity[j])?dist[<realCity[i],realCity[j]>]:dist[<realCity[j],realCity[i]>]);

int dist2b[i in Cities,j in Cities]=dist2[<i,j>];

dvar interval itvs[1..n+1] size 1;

dvar sequence seq in all(i in 1..n+1) itvs[i];

dvar sequence seq2 in all(i in 1..n+1) itvs[i] types all(i in 1..n+1)i;

// Gives which city is visited after city i
dvar int nextCity[1..n+1] in 1..n+1;

// Power 2
dvar int nextCity2[1..n+1] in 1..n;

// Power 3
dvar int nextCity3[1..n+1] in 1..n;

dvar int nextCity4[1..n+1] in 1..n;

 

execute
{

cp.param.TimeLimit=60;
var f = cp.factory;
  cp.setSearchPhases(f.searchPhase(seq));
}

tuple triplet { int c1; int c2; int d; };
{triplet} Dist = {
      <i-1,j-1,dist2[<i ,j >]>
           |  i,j in 1..n+1};

          
           
minimize endOf(itvs[n+1]) - (n+1);           
subject to
{
    startOf(itvs[1])==0; // break sym    
    noOverlap(seq,Dist,true);    // nooverlap with a distance matrix
    last(seq, itvs[n+1]); // last node
//    prev(seq, itvs[1], itvs[9]);
//    prev(seq, itvs[9], itvs[73]);
//    prev(seq, itvs[73], itvs[81]);
    //prev(seq, itvs[36], itvs[16]);
    sameSequence(seq,seq2);
    
    
    forall(i in 1..n+1) nextCity[i]==(typeOfNext(seq2,itvs[i],1)-1) mod n+1 ;
    
    forall(i in 1..n+1) nextCity2[i]==nextCity[nextCity[i]];
    
    forall(i in 1..n+1) nextCity3[i]==nextCity[nextCity2[i]];
    
    forall(i in 1..n+1) nextCity4[i]==nextCity[nextCity3[i]];
       
    forall(i in 1..n-1) dist2b[i,nextCity4[i]]<=3;

    nextCity[1]==8;
    nextCity[8]==57;
    nextCity[57]==64;

}
          
          
 int  x[<i,j> in Edges]=prev(seq,itvs[i],itvs[j])+prev(seq,itvs[j],itvs[i]);
 int  isPrevFromNPlus1[i in 1..n]=prev(seq,itvs[i],itvs[n+1]);
 int l=first({i | i in 1..n : isPrevFromNPlus1[i]==1});
 edge el=<1,l>;
 
 execute
 {
 isPrevFromNPlus1;
 x;
 x[el]=1;
 }
 
 // Let us check here that the constraints of the IP model are ok
 assert forall (j in Cities)
        as:sum (<i,j> in Edges) x[<i,j>] + sum (<j,k> in Edges) x[<j,k>] == 2;
        
// Let us compute here the objective the IP way
int cost=sum (<i,j> in Edges) dist[<i,j>]*x[<i,j>];

execute
{
writeln(cost);
}       

 

and the data is attached in a file called Alex.  

Now the solution start by visiting cities 1, 8, 57, and 64 as instructed. the 5th city visited is 20 and d(1,20) is 3 so that okay. the 6th city visited is 21 and d(8,21)=2 so that is good. the 7th node visited is 35 and d( 57,35) =3 which is also okay. the problem arises on the 8th visit which is node 34 and with the same trace back logic we used with the other nodes d(64,34) should be less than or equal to 3 but it is actually 6, and that is violates our constraint where d is 3. After that it gets messy and it visits city 42 that is not even near node 20 that was visited 4 steps before

I feel like it is a problem with sequencing and number more than a logical thing, since it works well for the first few cities 

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi

if I add

assert forall(i in 1..n-1) dist2b[i,nextCity4[i]]<=3;

after the subject to I do not get any error

Moreover

int check=max(i in 1..n-1) dist2b[i,nextCity4[i]];
execute
{
writeln("check=",check);
}

gives

 

check=3

regards

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Ashraf_ISE

I feel so sorry for this back and forth, and I do appreciate your help big time. I'm attaching a screenshot of the output solution 

It's blowing my mind because the sanity check you did works perfect and it returns 3 as intended. BUT as you can see in the attached screenshot, the value of nextCity4[64] = 34 but from dist2b d(34,64) = 6. so that shouldn't be part of the solution. I'm also wondering how come check=max(i in 1..n-1) dist2b[i,nextCity4[i]] returns 3 where clearly at least we have one case where it's 6

#DecisionOptimization
#OPLusingCPLEXOptimizer

This post was removed

This post was removed

This post was removed