Originally posted by: PhilDac

Hello,

I am new in this forum. So this question might seem easy to you, but your help is really important to me.

I am modelling an allteration of the Travelling Salesman Problem and im using the classic Subtour Elimination Constraint by Dantzig et al. 

At that moment I modelled every combination for this contstraint by hand...

For a larger number of cities n I need an automatic formula to create those constraints

The formulas:

sum ( i in S, j in S) x[i][j] < cardinality of S 

with S as being all possible subsets of the set  I 

now those subsets grow really fast with every additional city

is there a way to modell this in a comprehensive way? 

thank your very much for any help

#CPLEXOptimizers
#DecisionOptimization

Unless you want to dynamically separate the constraints you need to generate the powerset of I. Generating a powerset has been discussed various times on this Forum, see for example here and here. You may also want to search (or ask) the OPL Forum.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: PhilDac

Hello Daniel, 

thank your very much for your help! The powerset is just what I was looking for!

But now I cant really access the single arrays in between the set...

I implemented the superset as follows:

{int} I = {0,1,2,3,4,5,6,7};

range r=1.. ftoi(pow(2,card(I)));

and it works!

 

but how can I access the arrays in an constraint during the optimization process?

That s what I tried:

But the forall statement cant be used for sets of arrays... Do you know how to solve this problem? Im really stuck at that point

 

Thank you very much again in advance!!

Kindest regards

 

#CPLEXOptimizers
#DecisionOptimization

I think this is what you want:

forall(k in r : card(s2[k]) > 1 && card(s2[k]) < card(I) - 1) {
    sum(i in s2[k], j in s2[k]) x[i][j] <= card(s2[k]) - 1;      
}

You may also want to set Language->Run->Export format to "LP" and check the create .lp file that your constraints look as expected.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: PhilDac

Thank you very much! That is exactly what I was looking for! Great to have people like you helping one out!!

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: max__x

Dear Phil,

I am facing the same problem as you did, can you send the code you did for the subtour elimination ?

I will very appreciate it !

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sophieTSP

I would like to solve a derivative of the problem of probabilistic traveling salesman problem (clients are stochastic), with a decision variable with 3 indices: i, j and k, I have a problem that I go beyond a size of 5, the program gets locked during 'execusion with a size of 5 the results are accurate, but more than 5 he is blocking

/*********************************************
 * OPL 12.8.0.0 Model
 * Author: dell
 * Creation Date: 28 mars 2018 at 14:48:28
 *********************************************/
int     n       = ...;
int     nbs    = ...;
 
 range Scs=1..nbs;
 range Cities=1..n;
 

    
    
{int} I = {1,2,3,4,5};
range r=1.. ftoi(pow(2,card(I)));
{int} s [k in r] = {i | i in I: ((k div (ftoi(pow(2,(ord(I,i))))) mod 2) == 1)};
execute
{
 writeln(s);
}

tuple t
 {
 {int} set;
 };
 
 {t} res={<s[k]> | k in r : 1<=card(s[k])<=card(I)-1};
 
 execute
 {
 writeln(res);  
 }
 
 int percentage=80;
 
 int P[h in Scs][i in Cities]=rand(100);
 
 int S[h in Scs][i in Cities]=(P[h][i]>=percentage)?0:1;
 
 execute
 {
 writeln(S);
 } 
 
 int l[i in Cities][j in Cities] = (i==j)?0:rand(100);
      execute
 {
 writeln(l);
 }   

dvar boolean x[Scs][Cities][Cities];
dvar boolean y[i in Cities][j in Cities];
 
 minimize sum (i in Cities, j in Cities, h in Scs: i!=j)(l[i][j]*x[h][i][j])/nbs;
    subject to
    {
    forall (j in Cities)
    sum (i in Cities : i!=j) y[i][j] ==1;
    forall (i in Cities)
    sum (j in Cities : j!=i) y[i][j] ==1;  
    
       
    forall(j in Cities,h in Scs: S[h][j]==1)
    sum (i in Cities : i!=j  ) x[h][i][j] ==1;
             
    forall(i in Cities,h in Scs: S[h][i]==1)
    sum (j in Cities : j!=i ) x[h][i][j] ==1;
    
    forall(k in r : card(s[k]) > 1 && card(s[k]) < card(I) - 1) 
    sum(i in s[k], j in s[k]) y[i][j] <= card(s[k]) - 1; 
         
forall(h in Scs, k in r : card(s[k]) > 1 && card(s[k]) < card(I) - 1) 
    sum(i in s[k], j in s[k]) x[h][i][j] <= card(s[k]) - 1;      

 forall( i in Cities,j in Cities , h in Scs :S[h][i]==S[h][j]==1 ){
   
 x[h][i][j] >=  y[i][j];} } 

    
    can you help mee
       
 
 
 
 
 
 
 
 
 
 
 

#CPLEXOptimizers
#DecisionOptimization

Which values do you use for 'n' and 'nbs' in your model? What is the element that you increase beyond 5 when things go bad? Is that 'I'?. And where is it blocked? Do you see anything in the scripting or the engine log?

I tried running your .mod file here with some values for 'n', 'nbs' and 'I'. Everything worked fine. Can you post a .mod/.dat file that causes trouble for you?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sophieTSP

the problem is in the Set I: normally when I have a size n = 20 for example, it is necessary to write {int} I = {1,2,3,4,5,6,7,8,9, 10,11,12,13,14,15,16,17,18,19,20};
n: is the number of customers
nbs: is the number of scenarios
S is the scenario matrix
when I have this size, the execution is blocking '' the calculation does not stop and at the end a little message is displayed: problem opl Run

#CPLEXOptimizers
#DecisionOptimization

Are you aware that for 20 customers you will have to create 2^20=1048576 subsets/constraints for the subtour elimination constraints? This may eat a lot of memory and time. Could it be that you just hit a memory limit? If you plan to take this even further than you may have to think about dynamic constraint separation or a different formulation.

I also wonder whether your subtour elimination constraints for the x variables are correct. Shouldn't they be defined only over the cities that exist in the respective snapshot (at least that is how I read your math programming formulation in the attached image). I would have expected something like this (but maybe I am wrong):

int SCities[h in Scs] = sum(i in Cities) S[h][i];                 /* Number of cities in scenario h. */
int exists[h in Scs][k in r] = min(i in s[k]) S[h][i];            /* Does subset s[k] exist in scenario h?
                                                                   * This is only true if all cities in the subset
                                                                   * exist in scenario h, that is, if all S[h][i]=1
                                                                   * for all the cities in the subset. */

...

forall(h in Scs, k in r : exists[h][k] == 1 && card(s[k]) > 1 && card(s[k]) < SCities[h] - 1)
  sum(i in s[k], j in s[k]) x[h][i][j] <= card(s[k]) - 1;

 

#CPLEXOptimizers
#DecisionOptimization

Also, printing out all those sets may take quite some time. Maybe remove the writelln() statements that dump whole sets or change them so that each statements prints only a single short line.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sophieTSP

hello 

I cant change the formulation , so how would I do with the dynamic constraint separation?

regards 

#CPLEXOptimizers
#DecisionOptimization

CPLEX comes with an example for dynamic subtour elimination in OPL. This example can be found in opl/models/TravelingSalesmanProblem. Can you please take a look at that?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sophieTSP

yes, I looked but I don't know how to add the third scenario index k in this constraint  (constraint 7)

// Subtour elimination constraints.
    forall (s in subtours)
        sum (i in cities : s.subtour[i] != 0)
           x[minl(i, s.subtour[i]), maxl(i, s.subtour[i])]
           <= s.size-1;
           
 };

 

 

#CPLEXOptimizers
#DecisionOptimization

I am not sure but isn't it enough to have subtour elimination constraints on the y variables? And these variables don't have a scenario index. So in the quoted code just replace x by y and be done.

If it turns out that your per-scenario solutions contain subtours then you will have to separate subtour elimination constraints for x as well. In that case you have wrap the whole separation code (the code finding the subtours and the code generating the constraints) into a loop that loops over all scenarios. This will give you the scenario index (the loop variable) so that you can reference the x variables.

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sophieTSP

Hello

I am new in OPL and I work on a mathematical model of Traveling Salesman Problem with variable customers, I would like to make the resolution with OPL CPLEX, I have seen the resolution of the classic TSP with the DFJ formulation, and in my case I wonder how I could introduce a new parameter (Scenario) since it is stochastic in the source code of the Classic TSP ( Subtour Elimination Constraincts) , the formulation is as follows:

I started writing the code but i have difficulty to integrate the scenario concept into the code

// Cities

 int     n       = ...;

 int     nbScs    = ...;

 

 range Scs =1..nbScs;

 range Cities  = 1..n;

  

{int} I = {1,2,3,4,5};

range r=1.. ftoi(pow(2,card(I)));

{int} s2 [k in r] = {i | i in I: ((k div (ftoi(pow(2,(ord(I,i))))) mod 2) == 1)};

execute

{

 writeln(s2);

}

 

 // more than two elements and less than |S|-1 elements

 tuple t

 {

 {int} set;

 };

 

 {t} res={<s2[k]> | k in r : 2<=card(s2[k])<=card(I)-1};

 

 execute

 {

 writeln(res);  

 }

 

 // Edges -- sparse set

 int         l[i in Cities][j in Cities] = ...; 

 int         S[k in Scs][i in Cities ][j in Cities] = ...;

 

 

  

 

 // Decision variables

 dvar boolean y[i in Cities][j in Cities];

 dvar int+ x[k in Scs][i in Cities][j in Cities] ;

 

 

 // Objective

 minimize sum (i in Cities, j in Cities, k in Scs: i!=j) l[i][j]* x[k][i][j];

 subject to {

    

    // Each city is linked with two other cities

         forall (j in Cities)

         flow_in:

         sum (i in Cities : i!=j) y[i][j] ==1;

         

         forall (j in Cities, k in Scs)

         sum (i in Cities : i!=j ) x[k][i][j] ==1;

                

   

    forall (i in Cities)

         flow_out:

         sum (j in Cities : j!=i) y[i][j] ==1;

         

         forall (i in Cities, k in Scs)

         sum (j in Cities : j!=i , k in Scs) x[k][i][j] ==1;  

               

         

   // Subtour elimination constraints.

    

    forall( k in r: 1 < card(s2[k]) < card(Cities) - 1 ) {

    sum(i in s2[k], j in s2[k]) y[i][j] <= card(s2[k]) - 1; }

     forall(k in Scs ,c in r : card(s2[c]) > 1 && card(s2[c]) < card(I) - 1) {

    sum(i in s2[c], j in s2[c],k in Scs) x[k][i][j] <= card(s2[c]) - 1;      

}

 forall(i in Cities, j in Cities , k in Scs){

 

  x[k][i][j]<=y[i][j];}

 

 

};  

 

please I need your help

#CPLEXOptimizers
#DecisionOptimization

similar question at https://www.ibm.com/developerworks/community/forums/html/topic?id=16cd11a9-ce30-41fa-9259-ed543b4b8243&ps=25

#CPLEXOptimizers
#DecisionOptimization