Topic
  • 4 replies
  • Latest Post - ‏2015-01-14T14:24:26Z by AlexFleischer
Stefano_TUE
Stefano_TUE
1 Post

Pinned topic TSP - subtour elimination constraints

‏2012-05-23T13:01:26Z |
Hello,

I have a problem for the input data to the following problem:

http://pic.dhe.ibm.com/infocenter/oplinfoc/v6r3/topic/ilog.odms.ide.help/examples/html/opl/models/TravelingSalesmanProblem/tsp.mod.html

It is a TSP formulation from the OPL samples.

My doubt is how the data of the instance should be written for the tuple:

034: tuple Subtour { int size; int subtourCities; }
035: {Subtour} subtours = ...;

This tuple is related to the subtour elimination constraints.

If you have any TSP.dat, it would be very useful.

Thanks
Stefano
Updated on 2012-12-24T08:05:48Z at 2012-12-24T08:05:48Z by SystemAdmin
  • davidoff
    davidoff
    6 Posts

    Re: TSP - subtour elimination constraints

    ‏2012-05-25T16:50:07Z  
    Hello

    In the sample, the subtours are initially set to an empty collection in the params.dat file. Then subtours are detected in the postProcess and we keep the smallest subtour and resolves the model.

    You can display the last subtour added to the MIP
    
    dat.subtours.add(opl.newSubtourSize, opl.newSubtour); writeln(
    "Last subtour added : ",Opl.last(dat.subtours));
    //add this to display the last subtour
    


    For instance, the first subtour is
    
    <3 [0 0 14 0 0 0 0 0 0 0 0 0 0 15 3 0 0]>
    


    which means that we have found a subtour of 3 cities, namely cities 3 (with successor 14) ,14 (with successor 15) and 15 (with successor 3)

    If you want to add initial known subtours, you can set additional sets in params.dat

    David
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: TSP - subtour elimination constraints

    ‏2012-12-24T08:05:48Z  
    • davidoff
    • ‏2012-05-25T16:50:07Z
    Hello

    In the sample, the subtours are initially set to an empty collection in the params.dat file. Then subtours are detected in the postProcess and we keep the smallest subtour and resolves the model.

    You can display the last subtour added to the MIP
    <pre class="jive-pre"> dat.subtours.add(opl.newSubtourSize, opl.newSubtour); writeln( "Last subtour added : ",Opl.last(dat.subtours)); //add this to display the last subtour </pre>

    For instance, the first subtour is
    <pre class="jive-pre"> <3 [0 0 14 0 0 0 0 0 0 0 0 0 0 15 3 0 0]> </pre>

    which means that we have found a subtour of 3 cities, namely cities 3 (with successor 14) ,14 (with successor 15) and 15 (with successor 3)

    If you want to add initial known subtours, you can set additional sets in params.dat

    David
    forall (s in subtours)
    sum (i in Cities : s.subtour[i] != 0)
    x[<minl(i, s.subtour[i]), maxl(i, s.subtouri])>
    <= s.size-1;
    excuse me, i have some questions obout the code obve. Could you some explainnation about how the constraints make effects on the TSP problem.
    I would aprreciate your help very much.
  • max__x
    max__x
    13 Posts

    Re: TSP - subtour elimination constraints

    ‏2015-01-13T21:39:23Z  
    • davidoff
    • ‏2012-05-25T16:50:07Z
    Hello

    In the sample, the subtours are initially set to an empty collection in the params.dat file. Then subtours are detected in the postProcess and we keep the smallest subtour and resolves the model.

    You can display the last subtour added to the MIP
    <pre class="jive-pre"> dat.subtours.add(opl.newSubtourSize, opl.newSubtour); writeln( "Last subtour added : ",Opl.last(dat.subtours)); //add this to display the last subtour </pre>

    For instance, the first subtour is
    <pre class="jive-pre"> <3 [0 0 14 0 0 0 0 0 0 0 0 0 0 15 3 0 0]> </pre>

    which means that we have found a subtour of 3 cities, namely cities 3 (with successor 14) ,14 (with successor 15) and 15 (with successor 3)

    If you want to add initial known subtours, you can set additional sets in params.dat

    David

    Hello, David

    I have the same problems as Stefano,  

    does this what you mean here ?

     tuple subtour { int size; 
                    int subtour[cities]; }
     {Subtour} subtours = ...;
    dat.subtours.add(opl.newSubtourSize, opl.newSubtour); writeln(
    "Last subtour added : ",Opl.last(dat.subtours));

    and set the initial subset to be empty?

    Is the code used in CPLEX?

    because there still some mistake in the code. such as the unexpected "." after dat  and writeln I bold.

     

     

     

  • AlexFleischer
    AlexFleischer
    43 Posts

    Re: TSP - subtour elimination constraints

    ‏2015-01-14T14:24:26Z  
    • max__x
    • ‏2015-01-13T21:39:23Z

    Hello, David

    I have the same problems as Stefano,  

    does this what you mean here ?

     tuple subtour { int size; 
                    int subtour[cities]; }
     {Subtour} subtours = ...;
    dat.subtours.add(opl.newSubtourSize, opl.newSubtour); writeln(
    "Last subtour added : ",Opl.last(dat.subtours));

    and set the initial subset to be empty?

    Is the code used in CPLEX?

    because there still some mistake in the code. such as the unexpected "." after dat  and writeln I bold.

     

     

     

    same thread at https://www.ibm.com/developerworks/community/forums/html/topic?id=45075e99-c6b9-447f-94da-4b8124f0662c&ps=25