help-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Help-glpk] Need some help: very urgent


From: Mudassar Majeed
Subject: [Help-glpk] Need some help: very urgent
Date: Mon, 17 Oct 2011 17:13:14 -0700 (PDT)

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]