第一遍读的时候觉得自己不迷茫, 第二遍就迷茫了.

lp和ip的基础
  • 线性规划松弛和紧绷的约束条件, 然后单纯形替换紧绷的约束条件. 这里需要一个好的入门书, 作者有推荐, 不过貌似没有中文版.
  • 线性规划和他的对偶问题, 一定要理解.
    • 线性规划和对偶问题是同解的.
    • 线性规划和对偶问题互为参数和变量.
    • 目标函数的极值是相反的, 也就是说如果原问题是max, 那么对偶问题就是min.
曾经的迷茫点
  1. 闵可夫斯基定理
    1. 闵可夫斯基死的比单纯形早, 因此单纯形是对定理的应用.
    2. 所有的半空间包围的形状里面有最终的解.
    3. 单纯形法就是找到足够多的线性不等式, 拿到足够多的半空间限制.
    4. 最终找到解空间, 这个解空间就是一个n维的单纯形.
    5. 因此这个解法叫单纯形法.
    6. 总之闵可夫斯基的意思是, 一堆线性不等式可以把空间划出一堆半空间, 而这些半空间可以形成一个解空间, 这个解空间是个凸包, 这种凸包又叫单纯形.
  2. 闵可夫斯基定理的内容是:
    1. 一组点, 一定可以用其中的某些点为顶点, 形成一个凸包.
    2. 这个凸包包括点集中所有的点.
    3. 对照到tsp就是不等式永远在, 找到了就能分割出最后的解.
究竟怎么用lp解决tsp呢?

基础部分: 原问题和对偶问题:

  1. 原问题度约束, 就是个点的周围的边的和最多=2. 但是, 如果一条边直接=2其实是不合理的, 这意味着走了回头路. a->b->a.
    1. 用度约束配合单纯形求解, 这里就出现了, 0, 0.5, 1. 这个就是一个处理手法. 比0, 1, 2方式方便. 然后用这种方式, 我们发现0.5就是不大合理的项目了, 出现0.5意味着局部出现了环.
    2. 这个约束的目标是总路程最小.
  2. 对偶问题是: 2r1+2r2……. 最大值. r1(点1的半径)+r2(点2的半径)<c12(点1到点2的距离)
    1. 这个对偶问题, 要安排控制区(半径)
    2. 还要安排护城河 - 半径之间的巨大空隙.

和红线死磕, 这里关键是解决那些取值0.5的线.

  1. 子回路消除, 目标是消除孤立的团簇.
    1. 跨团簇的路径权重至少要=2. 对待团簇和对待点是一样的.
    2. 挑选子回路消除的方法叫: 割平面法.
    3. 子回路之后, 并没有消除0.5的线.
    4. 然后用4元素约束, 这个就是梳子不等式.
  2. 梳子不等式,
    1. k个齿, 一个柄, 路线数量是3k+1, k为奇数时.
    2. 梳子扩展出一系列概念;
      1. 多个炳的团树.
      2. 包围凸包的小平面不等式.
  3. 小平面不等式:
    1. 子回路不等式
    2. 梳子不等式
    3. 团树不等式

分离问题

  1. 什么是分离问题:
    1. 线性规划的不等式再面临大规模tsp问题时, 几乎是无穷无尽的.
    2. 因此, 分离是一个重要的问题, 他从已知的的不等式中找到不满足的不等式, 也就是说有用的不等式.
  2. 最大流最小割
    1. 从起点开始逐点校验. 直到终点.
    2. 由最小割产生的每个子图的最大流都是2.
    3. 任取一个源点. 依次以所有剩下的点位汇点, 所有的最大流都是2, 则已经满足了所有的子回路不等式.
    4. 最小割其实就是子回路消除的分离问题.
  3. 梳子的分离问题
    1. 多米诺奇偶性不等式就在这里了.
  4. 图的完美匹配问题
    1. 两个顶点构成且只构成一条边, 这就是一个匹配.
    2. 完美就是, 权重(可以认为是距离)和最小的边构成.
    3. 再tsp这个领域, 一个图里面所有点都是联通的.
    4. 然后我们找出几乎包含所有点的匹配(如果是奇数点, 必然漏一个点.)
    5. 然后要求这些匹配的权重总和最小.
    6. 书中的完美匹配其实是是准完美匹配的定义: https://zh.wikipedia.org/wiki/匹配_(图论)
    7. edmonds的伟大工作没有找到中文资料, 英文很好: https://en.wikipedia.org/wiki/Blossom_algorithm
    8. 他考虑的是奇数点构成的一个簇, 必然后遗漏一个点要对外做一个匹配. 这个不等式和子回路不等式很像, 不过他要求的是1, 只要有一个匹配联通就好, 子回路要求的是2.
    9. 因此, 每个奇数点构成的子包都有一个不等式, 也就是一个割平面.
    10. 这些割平面得到的凸包, 就是完美匹配的凸包. 好牛好牛.

处理红线的另一个主要思路

  1. 分支定界依旧是处理红线(值为0.5的线)的方法
    1. 两条路, 一条用这个红线, 一条不用这个红线.
    2. 然后分别计算, 就可以抛弃一个.
  2. 最终分支定界和割平面结合起来, 分支切割法.
从复杂度的角度考虑

哈密尔顿回路和二分图(bipartite)或许更贴近现实问题

  • 比如快递包裹需要取和派, 这个用二分图描述是非常直观的想法.

动态规划算法是2的n次方的时间开销, 这个值得实现一下.

  • held-karp算法, 这里我最大的问题是, 之前认为每一步之间的关系是乘法是类似排列组合的关系. 这个思路错了, 这个算法秒在每步的复杂度其实都是独立的, 整体复杂度等于每步复杂度的加法. 是一个标准的西格玛(求和的那个很大的符号).
旅行商的代码领域
  • concorde
  • LKH
迷茫啊迷茫
  • 子回路消除的时候, 为啥可以不是整数?
  • 度消除, 就是每个点连接的线只有两条, 这个是0, 1, 2 三个解, 确切的说只有0和1. 因为2是死路, 等于a->b,然后立刻b->a.
  • 但是, 多个团, 每一对团之间, 必须为2, 这个解可以出现分数. 为什么呢?
  • 因为这样可以保证解一定存在, 取值: 0, 0.5, 1的解.
  • 其实度约束的情况是一样的, 如果不给0.5, 会出现极度不合理的解.
  • 每个解都是一个下限. 所以每个点都只能连接最近的和次近的点, 特殊情况可以连接第三近的点, 不然解就不对了. 比如48点的图, 左上角有3个0.5的线. 右上角也是. 不然线就断了.
约束像天上的星星一样多
  • 度消除的数量不多, 等于点的数量.
  • 但是子回路消除的数量就像星星一样多了.

很棒的参考资料: http://www.math.uwaterloo.ca/tsp/index.html