0

我正在玩 GLPK 提供的旅行推销员示例，并试图了解我可以合理期望解决的问题规模。我已经设法解决了一个 50 个节点的图，但是 100 个节点似乎并没有在合理的时间范围内收敛（现代硬件上 30 分钟左右）。

GLPK 有很多 MIP 求解器的选项。我尝试了各种组合，但我完全不清楚哪些选项可能会有所帮助。此页面有一些讨论，但有些过时，建议相当笼统。

期望 GLPK 在实际时间范围内（例如，少于 4 小时）解决 100 个或更多节点的旅行是否合理？问题规模何时变得棘手？许多命令行选项中的任何一个都可能有帮助吗？

4

2 回答 2

1

Are any of the many command-line options likely to help?

The tspsol command line applicaton (based on the GLPK C library) or the C API in glptsp.h are tailor-made for solving TSP.

Is it reasonable to expect GLPK to solve a 100 node tour or greater in a practical time frame (say, less than 4 hours)? When does the problem size become intractable?

My guess is that it also greatly depends on the problem instance as well. If you look into the C code, you will see that heuristics are used to generate an initial tour. How well a heuristic works, well...

I assume you know that the TSP is famous for being difficult to solve, see computational complexity.

于 2013-08-25T19:42:39.157 回答
1

我能够在 2 秒内解决 eil51 并在大约 50 秒内解决 rat99，方法是从 TSP 的放松开始，然后消除子旅行，直到找到可行的解决方案。做一个更好的建模不仅仅是摆弄求解器选项。如果建模足够好，GLPK 应该能够处理更大的实例。eil51 和 rat99 是 TSPLIB 上记录的实例。

我建议阅读一些关于 tsp 建模的材料，那里有很多文章和书籍。一个不错的起点可能是 Der-San Chen 等人的“应用整数编程”。

于 2016-02-02T12:21:02.030 回答