[Top][All Lists]
[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
- [Help-glpk] Need some help: very urgent,
Mudassar Majeed <=