Outline
1. 数学规划应用与难度
2. COPT的LP开发流程图
3. COPT的IP开发流程图
4. 一点总结
======================
1. 数学规划应用与难度
预处理部分的主要工作就是识别一些变量或者消除一些约束，尽量固定一些变量，尽量减少一些约束。预单变量约束消除这个可能就是变成单变量上下界的形式。这个Presolve的东西有时候当我们需要特定结果时，需要人为关闭这个功能，否则有可能模型还没有到调用具体算法的阶段就被预处理直接求解完了。
具体求解的过程，正儿八经的线性代数的东西，A=LU的LU分解，L是lower triangular matrix, U是upper triangular matrix. 想想高斯消元法求解线性方程组的事情。
单纯形法里的Pivoting那个，只是一个环节。这个环节有很多启发式的东西，其实就是有很多非基变量可以进基时，选哪个？这个其实没有明确的结论，一般图省事，我们会用最简单的规则来选择满足需要的进基变量，比如最小下标规则。 先选哪个，再选哪个，这个事情整体上影响的是求解过程，也可以理解成迭代过程。有可能好的规则下，只需要迭代50步就完事了，差的规则下需要迭代100步。这个事情在列生成时也会遇到。 另外，就是还有循环那一茬，某个非基变量进基变成了基变量，有可能在后面的继续迭代过程中又被排挤出去了，后面的继续迭代过程中发现又被加进去了，就导致了循环，这个也是有一些规则的，防止循环。
单纯形法与内点法 单纯形法严格意义上讲不是多项式时间算法，是一个指数时间算法，但是它的实际表现，average performance不错。内点法才是严格意义上好的多项式时间算法，这个是有数学证明的。 现在大部分教材还是教单纯形法，一方面是因为它的表现不错，另外一方面是它有很好的几何结构和性质，而且很多高级算法都要依赖于单纯形法，比如Gomory’s cut就是从最优单纯形表里来，Column generation寻找满足条件的列也是参考单纯形表里的非基变量检验数的事情。而内点法powerful的地方在于首先是表现好是一方面，这个还能用来解非线性规划，这一点simplex method不行。
对于整数规划的精确求解而言，其实就只有3种方法，cutting plane, branch-and-bound, dynamic programming.其中割平面法与分支定界法是普适性的方法，而动态规划是适用于求解某一个特殊的问题，能划分阶段，能界定出来状态变量、决策变量什么的，而且得能刻画出来阶段之间的关系。
从发展历程上来看，是先有割平面法再有分支定界算法。割平面法参考Gomory’s fractional cut那个，把一个IP问题松弛成LP问题，再不停的加割，直到得到一个整数解为止。这个方法是有理论保证的，通过这种方式不停加割，最终一定能得到一个整数解。只是有可能每次加的割都是切割掉了一点点可行域，结果需要加很多很多割才能得到整数解，所以收敛很慢。所以对于割这个事情，一个很重要的研究就是每次去找一些强有效的割，尽可能多的切割可行域。对于IP问题而言，基本上所有算法的初衷都是尽可能地缩小可行域，以方便寻找。
分支定界这个是目前最基础、最核心的求解IP问题的算法框架，基本上但凡涉及到整数规划问题，都绕不过这个B&B去，哪怕那些高级算法column generation, row generation, benders decomposition等，其实都是在折腾一个个的node，最外层还是得包一层B&B. 但凡以Branch-and-XXX命名的算法，最外层都是B&B，内核上都是在折腾一个个的node，而折腾node的目的是为了得到更好的upper bound或者lower bound, 从而在B&B tree上进行尽可能多的剪枝操作。 B&B tree的搜索过程就是去求解一个个的node, 每个node都是一个LP model.如果没有什么其他技巧的话，对于一个min问题而言，每个node求解得到的非整数解就是下界，碰巧找到的整数解就是上界，整数解是用来剪枝的。
求解器的控制台输出，一行对应着一个节点，如果这一行上有“H”或“*”的标记，表明求解器在求解这个node时用了一些heuristic的技巧，或者取整了，或者加了什么cut，从而得到了整数解。这些技巧是发生在node上的。 而对于B&B本身而言，核心的东西就2个，(1) 选择分支变量；(2) 选择节点。这里有很多技巧。但是不管是什么技巧，目的都是为了剪枝，为了尽可能地减少B&B tree的node数量。
B&B + cutting plane组合起来，就是branch-and-cut了，这个是目前所有求解器都在用的解整数规划的框架。 B&C = Branch-and-Cut B&P = Branch-and-Price, 这个price的事情是发生在node内部的，解子问题付出的代价。 B&P&C = Branch-and-Price-and-Cut B&BC = Branch-and-Benders cut 大部分高级算法都是在折腾node里面的求解过程，目的是为了得到更好的上界或下界。而B&B本身是那个分支定界树，这里的技巧是在分支定界树上怎么遍历。这是两个不同的层级。
做整数规划精确算法相关的研究，要发paper，设计开发的算法肯定要比求解器好才行，否则没有意义。
对于求解器而言，在解一个模型时，它能够通过一些预处理来收紧变量的界，或者减少一些冗余约束，也能识别一些特定的约束结构，从而调用一些针对性的加割模块，以加速求解。但是对于求解器而言，它不会识别变量本身的意义，也不在意什么第一阶段、第二阶段（这个可能就是人与机器的区别）
比如对于选址路径问题而言，我们可能用变量y表现选址决策，x表示路径决策，对于这类问题我们会考虑如果这个事情能够先选址再决策路径，对问题进行分解，整个事情也许会被简化。或者对于一个模型的约束而言，我们能够理解某个约束，比如那些耦合约束，这些东西就是导致问题复杂难求解的原因，我们会考虑能否通过拉格朗日松弛的方式把这个难点给处理掉，从而降低问题的难度。
对于每一个复杂的问题，做出来模型之后，上求解器，发现很难求解，才有做研究的必要。而识别计算瓶颈，具体明确这个问题为什么求解起来这么费劲，是什么约束很复杂，还是说什么变量的取值有什么特点等，进一步怎么处理这些困难点，这就是做研究本身了。
对于复杂问题设计一些复杂的算法，往往是基于分解的路线来做。如果只是套用某些分解框架的话，很有可能整体上求解下来，还不如求解器硬解来的快。设计一个好的算法，往往是方方面面都要考虑，比如核心是分解，再加上很多其他技巧，这样才有可能超过商业求解器。
把事情做到极致，这也是个很艺术的事情。
整数规划的建模与求解都是挺有艺术性的事情。
