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