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

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
    63 Posts
    ACCEPTED ANSWER

    Re: Traveling Salesman Problem

    ‏2013-06-03T05:13:55Z  in response to RithulKrishnan

    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
      ACCEPTED ANSWER

      Re: Traveling Salesman Problem

      ‏2013-06-03T13:34:26Z  in response to DanielJunglas

      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
        ACCEPTED ANSWER

        Re: Traveling Salesman Problem

        ‏2013-06-03T16:03:06Z  in response to RithulKrishnan

        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
          63 Posts
          ACCEPTED ANSWER

          Re: Traveling Salesman Problem

          ‏2013-06-04T06:12:52Z  in response to RithulKrishnan

          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
            ACCEPTED ANSWER

            Re: Traveling Salesman Problem

            ‏2013-06-06T03:46:02Z  in response to DanielJunglas

            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
              63 Posts
              ACCEPTED ANSWER

              Re: Traveling Salesman Problem

              ‏2013-06-10T12:58:53Z  in response to RithulKrishnan

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

              • RithulKrishnan
                RithulKrishnan
                10 Posts
                ACCEPTED ANSWER

                Re: Traveling Salesman Problem

                ‏2014-04-20T07:48:37Z  in response to DanielJunglas

                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