TSP2019项目专注于使用MATLAB编写和执行解决旅行商问题(TSP)的算法。该项目通过优化循环结构,提高了解决大规模TSP实例的效率与准确性。
在Matlab环境下复现论文中的TSP2019问题求解代码包括两个主要部分:问题18与问题19。
对于问题18:
- 该问题是通过ADMM算法(交替方向乘子法)和改进的内点方法(IPM)来解决。
- ADMM目前仅包含一个框架,用于无约束优化问题的解决方案尚未确定。
- 改进IPM在CVX环境下基本完成但仍有部分需要调整。要运行此算法,请执行`IPM.m`文件。
对于问题19:
- 该问题是通过循环求解并在CVX环境中设置最大迭代次数为1来解决,可以通过修改`sdp`的‘maxit’参数实现。
- 此外,问题19具有解析解,因此使用函数`problem19.m`可以轻易地得到结果。
当前代码组织较为杂乱,并且存在多个独立的函数。后续计划对这些文件进行整理优化以提高可读性和维护性。此外,在部分地方使用了杨老师的toeplitz矩阵范德蒙德分解函数,即VanDec.m, 其中最后需要将phase替换为angle。
代码运行在Ubuntu18.04操作系统和Matlab2019b版本上,并且采用了CVX 2.2工具箱。硬件环境包括Intel处理器以及64GB内存。