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 <[email protected]> > An: "[email protected]" <[email protected]> > 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 _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
