Re: [Help-glpk] Need some help: very urgent

[glpk xypron]

Hello Mudassar,

the normal way to solve small traveling salesman problems is:

Solve the LP problem without subtour constraints. 
Identify subtours.
Add subtour constraints.
Resolve the LP
Repeat the last two steps until no new subtour arises.

See
http://www.tsp.gatech.edu/methods/opt/subtour.htm

A good book on the topic is
David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook
The Traveling Salesman Problem: A Computational Study 

Best regards

Xypron


-------- Original-Nachricht --------
> Datum: Mon, 17 Oct 2011 17:13:14 -0700 (PDT)
> Von: Mudassar Majeed <address@hidden>
> An: "address@hidden" <address@hidden>
> Betreff: [Help-glpk] Need some help: very urgent

> Hello people, 
>                        I am trying to solve Traveler
> salesman problem (TSP) using ILP (GLPK). Here is the code
> 
> /* Set of vertices or cities */
> 
> set V;
> 
> set S;
> set T;
> 
> /* Weights assigned to edges */
> 
> param w{i in V,j in V};
> 
> /* x{i,j} denotes whether edge {i,j} is existing in the selected path */
> 
> var x{i in V, j in V}, binary;
> 
> /* Shortest Path */
> 
> minimize path: sum{i in V, j in V} w[i,j] * x[i,j];
> 
> /* Subjected to: Every vertex has degree 2 */
> 
> s.t. atob{i in V}: sum{j in V: j <> i} x[i,j] = 1;
> s.t. btoa{i in V}: sum{j in V: j <> i} x[j,i] = 1;
> 
> /* Subjected to: Eliminate sub-tour */
> 
> s.t. ele_sub_tour_stot: sum{i in S, j in T} x[i,j] >= 1;
> s.t. ele_sub_tour_ttos: sum{i in S, j in T} x[j,i] >= 1;
> 
> /* End of code */
> 
> if you see the last two constraints, I wanted two sets S and T where S is
> a subset of V such that 2 <= |S| <= |V| -1 and T = V - S, this will make
> sure that sub-tour is eliminated.
> But I am not understanding how to define set S and T here. Some body
> please help me. I am trying to solve it using glpsol.
> 
> regards,
> Mudassar

-- 
Follow me at http://twitter.com/#!/xypron

Empfehlen Sie GMX DSL Ihren Freunden und Bekannten und wir
belohnen Sie mit bis zu 50,- Euro! https://freundschaftswerbung.gmx.de