【组合优化】旅行商问题Traveling Salesman Problem(TSP)-解的最优性证明

上一节使用的求解旅行商问题的方法为：整数线性规划算法intlinprog

options = optimoptions('intlinprog');

整数线性规划算法中使用的为分支定界算法branch-and-bound algorithm。

分枝界限法是由三栖学者查理德·卡普（Richard M.Karp）在20世纪60年代发明，成功求解含有65个城市的旅行商问题，创当时的记录。“分枝界限法”把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解。

output.absolutegap的含义为：

Difference between upper and lower bounds of the objective function that intlinprog calculates in its branch-and-bound algorithm.

解释为分支定界方法中上界与下界的差值，若此值为0，则说明找到了一个最优解。

针对上一节的特定的旅行商问题：

disp(output.absolutegap)

结果为0。说明找到了一个最优解。

---

官方解释如下：

Solution Quality
The solution represents a feasible tour, because it is a single closed loop. But is it a minimal-cost tour? One way to find out is to examine the output structure.
disp(output.absolutegap)

0
The smallness of the absolute gap implies that the solution is either optimal or has a total length that is close to optimal.