Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only
  • 1.  Traveling Salesman Problem

    Posted 06/03/13 12:09 AM

    Originally posted by: RithulKrishnan


    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 


    #DecisionOptimization
    #MathematicalProgramming-General


  • 2.  Re: Traveling Salesman Problem

    Posted 06/03/13 01:14 AM

    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.


    #DecisionOptimization
    #MathematicalProgramming-General


  • 3.  Re: Traveling Salesman Problem

    Posted 06/03/13 09:34 AM

    Originally posted by: RithulKrishnan


    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.


    #DecisionOptimization
    #MathematicalProgramming-General


  • 4.  Re: Traveling Salesman Problem

    Posted 06/03/13 12:03 PM

    Originally posted by: 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?


    #DecisionOptimization
    #MathematicalProgramming-General


  • 5.  Re: Traveling Salesman Problem

    Posted 06/04/13 02:13 AM

    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.


    #DecisionOptimization
    #MathematicalProgramming-General


  • 6.  Re: Traveling Salesman Problem

    Posted 06/05/13 11:46 PM

    Originally posted by: RithulKrishnan


    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?


    #DecisionOptimization
    #MathematicalProgramming-General


  • 7.  Re: Traveling Salesman Problem

    Posted 06/10/13 08:59 AM

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


    #DecisionOptimization
    #MathematicalProgramming-General


  • 8.  Re: Traveling Salesman Problem

    Posted 04/20/14 03:49 AM

    Originally posted by: RithulKrishnan


    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


    #DecisionOptimization
    #MathematicalProgramming-General