Topic
  • 7 replies
  • Latest Post - ‏2014-04-20T07:48:37Z by RithulKrishnan
RithulKrishnan
RithulKrishnan
10 Posts

Pinned topic Traveling Salesman Problem

‏2013-06-03T04:09:18Z |

Hi,

 

I'm trying to solve the traveling salesman problem as an MIP using the IBM ILOG IDE, and thanks to the example given I was able to. However, I want to show the sequence of variables selected, for e.g., if I have a 4 city problem, and my shortest route is 32 meters, and the route is 1-4-2-3-1, how do I show this route? Please help me with this problem.

 

Thank You,

 

Rithul 

  • DanielJunglas
    DanielJunglas
    117 Posts
    ACCEPTED ANSWER

    Re: Traveling Salesman Problem

    ‏2013-06-04T06:12:52Z  

    I looked at the time table example, and it looks very complicated. I just want to create a set that holds the cities selected in order in which they are visited, and display this set in the end. Could anyone tell me how to do this?

    How to do that highly depends on how your model looks like. What are the variables? What are the constraints?.

    In the traveling salesman example that is shipped with CPLEX Optimization Studio you could print the optimal tour by replacing this code in script

            if (opl.newSubtourSize == opl.n) {
              opl.end();
              cplex1.end();
              break; // not found
            }

    by something like this:

            if (opl.newSubtourSize == opl.n) {
              // This simply prints the selected edges.
              for (var e in opl.Edges) {
                if (opl.x[e] > 0.5) {
                  writeln(e.i, " -> ", e.j);
                }              
              }
              // This prints the tour as a cycle
              var c = 1;      // current city
              var lastc = -1; // city visited right before C
              write(c);
              while (true) {
                var nextc = -1; // next city to visit
                
                // Find the next city to visit. To this end we
                // find the edge that leaves city C and does not
                // end in city LASTC. We know that exactly one such
                // edge exists, otherwise the solution would be infeasible.
                for (var e in opl.Edges) {
                  if (opl.x[e] > 0.5) {
                    if (e.i == c && e.j != lastc) {
                      nextc = e.j;
                      break;
                    }
                    else if (e.j == c && e.i != lastc) {
                      nextc = e.i;
                      break;
                    }                                    
                  }              
                }
                
                // Write next city and update current and last city.
                write(" -> ", nextc);
                lastc = c;
                c = nextc;
                
                // Stop if we are back at the origin.
                if (c == 1) {
                  break;
                }               
              }            
                          
              opl.end();
              cplex1.end();
              break; // not found
            }

    If you have a different formulation of the model then the code to print the optimal tour will of course look completely different.

  • DanielJunglas
    DanielJunglas
    117 Posts

    Re: Traveling Salesman Problem

    ‏2013-06-03T05:13:55Z  

    OPL allows to post-process solutions using scripting statements. With such post-processing you can write out the desired information into the scripting log.

    Post-processing is explained in the time tabeling example in this section.

  • RithulKrishnan
    RithulKrishnan
    10 Posts

    Re: Traveling Salesman Problem

    ‏2013-06-03T13:34:26Z  

    OPL allows to post-process solutions using scripting statements. With such post-processing you can write out the desired information into the scripting log.

    Post-processing is explained in the time tabeling example in this section.

    Thank you Daniel, will the post-processing script show me the rote followed by the salesman? I'm new to programming so 'm finding it a little difficult to understand these commands and how they work.

  • RithulKrishnan
    RithulKrishnan
    10 Posts

    Re: Traveling Salesman Problem

    ‏2013-06-03T16:03:06Z  

    Thank you Daniel, will the post-processing script show me the rote followed by the salesman? I'm new to programming so 'm finding it a little difficult to understand these commands and how they work.

    I looked at the time table example, and it looks very complicated. I just want to create a set that holds the cities selected in order in which they are visited, and display this set in the end. Could anyone tell me how to do this?

  • DanielJunglas
    DanielJunglas
    117 Posts

    Re: Traveling Salesman Problem

    ‏2013-06-04T06:12:52Z  

    I looked at the time table example, and it looks very complicated. I just want to create a set that holds the cities selected in order in which they are visited, and display this set in the end. Could anyone tell me how to do this?

    How to do that highly depends on how your model looks like. What are the variables? What are the constraints?.

    In the traveling salesman example that is shipped with CPLEX Optimization Studio you could print the optimal tour by replacing this code in script

            if (opl.newSubtourSize == opl.n) {
              opl.end();
              cplex1.end();
              break; // not found
            }

    by something like this:

            if (opl.newSubtourSize == opl.n) {
              // This simply prints the selected edges.
              for (var e in opl.Edges) {
                if (opl.x[e] > 0.5) {
                  writeln(e.i, " -> ", e.j);
                }              
              }
              // This prints the tour as a cycle
              var c = 1;      // current city
              var lastc = -1; // city visited right before C
              write(c);
              while (true) {
                var nextc = -1; // next city to visit
                
                // Find the next city to visit. To this end we
                // find the edge that leaves city C and does not
                // end in city LASTC. We know that exactly one such
                // edge exists, otherwise the solution would be infeasible.
                for (var e in opl.Edges) {
                  if (opl.x[e] > 0.5) {
                    if (e.i == c && e.j != lastc) {
                      nextc = e.j;
                      break;
                    }
                    else if (e.j == c && e.i != lastc) {
                      nextc = e.i;
                      break;
                    }                                    
                  }              
                }
                
                // Write next city and update current and last city.
                write(" -> ", nextc);
                lastc = c;
                c = nextc;
                
                // Stop if we are back at the origin.
                if (c == 1) {
                  break;
                }               
              }            
                          
              opl.end();
              cplex1.end();
              break; // not found
            }

    If you have a different formulation of the model then the code to print the optimal tour will of course look completely different.

  • RithulKrishnan
    RithulKrishnan
    10 Posts

    Re: Traveling Salesman Problem

    ‏2013-06-06T03:46:02Z  

    How to do that highly depends on how your model looks like. What are the variables? What are the constraints?.

    In the traveling salesman example that is shipped with CPLEX Optimization Studio you could print the optimal tour by replacing this code in script

            if (opl.newSubtourSize == opl.n) {
              opl.end();
              cplex1.end();
              break; // not found
            }

    by something like this:

            if (opl.newSubtourSize == opl.n) {
              // This simply prints the selected edges.
              for (var e in opl.Edges) {
                if (opl.x[e] > 0.5) {
                  writeln(e.i, " -> ", e.j);
                }              
              }
              // This prints the tour as a cycle
              var c = 1;      // current city
              var lastc = -1; // city visited right before C
              write(c);
              while (true) {
                var nextc = -1; // next city to visit
                
                // Find the next city to visit. To this end we
                // find the edge that leaves city C and does not
                // end in city LASTC. We know that exactly one such
                // edge exists, otherwise the solution would be infeasible.
                for (var e in opl.Edges) {
                  if (opl.x[e] > 0.5) {
                    if (e.i == c && e.j != lastc) {
                      nextc = e.j;
                      break;
                    }
                    else if (e.j == c && e.i != lastc) {
                      nextc = e.i;
                      break;
                    }                                    
                  }              
                }
                
                // Write next city and update current and last city.
                write(" -> ", nextc);
                lastc = c;
                c = nextc;
                
                // Stop if we are back at the origin.
                if (c == 1) {
                  break;
                }               
              }            
                          
              opl.end();
              cplex1.end();
              break; // not found
            }

    If you have a different formulation of the model then the code to print the optimal tour will of course look completely different.

    Thank you Douglas, that code worked perfectly! I'm solving the TSP for 100 points, and after a few iterations the scripting log says error could not solve, is this because the IDE cannot handle large amounts of data?

  • DanielJunglas
    DanielJunglas
    117 Posts

    Re: Traveling Salesman Problem

    ‏2013-06-10T12:58:53Z  

    Thank you Douglas, that code worked perfectly! I'm solving the TSP for 100 points, and after a few iterations the scripting log says error could not solve, is this because the IDE cannot handle large amounts of data?

    Is it possible that your data is infeasible? What does the engine log say?

  • RithulKrishnan
    RithulKrishnan
    10 Posts

    Re: Traveling Salesman Problem

    ‏2014-04-20T07:48:37Z  

    Is it possible that your data is infeasible? What does the engine log say?

    Hi,

    I upgraded my RAM to 16GB and ran the TSP formulation (example problem) Cplex for a problem size of 142 components, and Cplex has taken 7 minutes. Is this normal? I was under the impression that it would take around 3-4 days. Also, when I run the berlin52.dat, Cplex solves in 0.64 seconds, whereas gr17.dat solves in 5 seconds. How is this possible, how can it take lesser time to solve a larger sized problem.

    Thank you,

    Rithul