zimpl 中的广义旅行商问题

Question

我是 zimpl 的新手，目前正在尝试为 GTSP 建模。设置是我们有被分组到集群中的节点。我的问题是我不知道如何在 zimpl 中实现哪个节点属于哪个集群。

到目前为止我做了什么：

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);

我猜有些东西不见了，因为我想在集群 1 中对节点 1,2、集群 2 中的 3,4 和集群中的 5,6 进行分组3.

也许有人可以提供帮助！谢谢

Answer 1

您可以使用索引集（就像您实现 C 的幂集一样）并根据需要分配集。例如试试这个：

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

使用以下行检查您输入的内容是否正确：

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

这将打印

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

到控制台。

Answer 2

如果您想从文件中读取集群-城市对应关系，ZIMPL user guide 中有一个详尽的部分介绍了如何实现这一点。不过，我认为它不能在一行中读取任意数量的条目。因此，我会将 GTSP 实例文件的集群部分转换为节点集群分配列表，即（以 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

我先变成

然后您可以阅读为：

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

zimpl 中的广义旅行商问题

Generalized Traveling Salesman Problem in zimpl

modeling

traveling-salesman

scip