Generalized Traveling Salesman Problem in zimpl

user_16177197 0
Viewed 142

I am new to zimpl and I am currently trying to modell the GTSP. The setting is that we have nodes which are grouped into clusters. My problem is i dont know how to implement in zimpl which node belongs to which cluster.

What I did so far:

set V:= {1..6}; set A:= {<i,j> in V*V with i < j};
set C:= {1,2,3};
set W:= {<p,q> in C*C with p < q};
set P[]:= powerset(C); set K:= indexset(P);

I am guessing something is missing because i want to group node 1,2 in cluster 1, 3,4 in cluster 2 and 5,6 in cluster 3.

Maybe someone can help! thanks

scip traveling-salesman modeling
2 Answers

You can use an indexed set (just as u did to implement the powerset of C) and assign the sets as needed. Try this for example:

set Clusters[C]:= <1> {1,2}, <2> {3,4}, <3> {5,6};

Use the following line to check your input for correctness:

do forall <p> in C do print Clusters[p];

This will print

List: |1|{<1>,<2>}
List: |1|{<3>,<4>}
List: |1|{<5>,<6>}

to the console.

user_65884930

If you want to read in the cluster-city correspondance from a file, there is an extensive section on how to achieve that in the ZIMPL user guide. I don't think it can read an arbitrary number of entries in a line, though. So I would instead convert the cluster-part of the GTSP instance file into a list of node-cluster assignments, i.e. (taking the example from here):

GTSP_SET_SECTION:
1 4 5 -1
2 1 2 3 10 11 12 13 14 -1
3 8 9 17 -1
4 6 7 15 16 -1

I would first turn into

1 4
1 5
2 1
2 2
2 3
2 10
...

Then you could read that in as:

members[C] := read "cluster.txt" as "<1n> 2n";
user_111583930
Related