在这篇文章中，我将对本系列之前的内容进行总结，并针对MIP的求解方法设计及求解器的使用给出一些个人理解和建议。
分支定界法的基本原理 How does B&B work?
对于一个（最小化）混合整数规划(MIP)问题
$$
\begin{equation}
\begin{aligned}
\min \ & c^T x \\
s.t. \ & Ax = b, \\
& l \leq x \leq u, \\
& x \in \mathbb{R}^{m_1} \times \mathbb{Z}^{m_2},
\end{aligned}
\label{eq:basic}\tag{1.1}
\end{equation}
$$
其对应的线性规划松弛(LP relaxation)问题是指放松问题\eqref{eq:basic}中的整数约束所得的规划问题。该问题可以通过单纯形法或内点法进行高效求解；所得的最优解虽然不一定是原MIP问题的可行解，但是相应的目标值可以作为MIP问题最优目标值的一个下界估计。
分支定界法(B&B)的基本原理是将上述LP松弛估计的思路与分治法(divide and conquer)进行结合，不断将原MIP问题切割成子问题并求解，以获得更准确的目标值下界估计和更好的可行解，直至找到最优解为止。具体来说，B&B流程不断重复以下步骤：
- 对于一个MIP子问题，求解其LP松弛问题，得到解$x$，并根据相应的目标值更新全局的目标值下界估计；
- 如果$x$不是MIP问题的可行解，那么从中选出一个不满足整数约束的变量$j$，并将该变量的可行域从原来的$[l_j,u_j]$切分为$[l_j,\lfloor x_j \rfloor]$和$[\lceil x_j \rceil,u_j]$，从而生成两个新的子问题；然后转到步骤4；
- 如果$x$是MIP问题的可行解，那么根据其目标值决定是否更新当前全局最优解(incumbent solution)，然后转到步骤4；
- 如果没有达到停止条件、且仍有未处理的子问题，则从中选择一个，然后回到步骤1。
我们也可以从一个更一般(general)的视角——“外部逼近”(outer approximation)——来理解B&B方法。具体来说，对于一个困难的优化问题
$$
\begin{equation}
\begin{aligned}
\min \ & f(x) \\
s.t. \ & x \in P, \\
\end{aligned}
\label{eq:general}\tag{1.2}
\end{equation}
$$
外部逼近的基本想法是将可行域$P$拆分为$\cup_{i=1}^{N} P_i$，对每个$P_i$找到一个容易计算的超集$\bar{P}_i \supset P_i$并在$\bar{P}_i$上求解优化问题，然后对各部分求解结果进行整合产生对原问题最优目标值的估计。通过不断切分$P_i$并降低$P_i$与$\bar{P}_i$之间的差距，我们可以令$\bar{P} = \cup_{i=1}^{N} \bar{P}_i$逐步逼近$P$，从而获得更准确的估计。特别地，如果在该“外部逼近”框架中，我们进一步通过切割变量取值范围来拆分可行域$P_i$，并令$\bar{P}_i$为$P_i$的relaxation，那么我们就得到了B&B方法。由于B&B方法只在坐标轴方向（变量取值范围）进行切分，相比一般的割平面效率不高；其他一些外部逼近方法，例如半正定规划(SDP)，可能可以给出更好的逼近效果。
MIP求解器的高效使用 How to use MIP solvers efficiently?
求解器的选用 Selection of Solvers
对于MIP问题，商用求解器（Gurobi/Cplex）通常比开源求解器（CBC）速度快1~2个数量级，而且接口、文档以及社区支持也更完善。因此，如果不需要考虑成本或者预算较多，可以直接选择商用求解器。
商用和开源求解器在MIP上的差距比在LP上的差距更大，主要有以下几点原因：
- 对LP问题的研究有较长的历史，相关求解算法非常成熟；相比之下，人们对MIP问题的理解仍然不够深入。
- MIP问题的复杂度和难度比LP问题高很多，（暂时）不存在单一最好的(single best)解法；因此，要在不同类型和场景的问题中都取得较好的效果，求解器往往需要从多个求解角度引入大量定制化(customized)/专门化(specialized)的技术，而这些工作需要更多的时间和金钱资源的投入。
不过，这也意味着对于特定类型问题，求解器不一定能给出最高效的解决方案；好的业务理解和问题建模往往更重要。
求解器配置的选用 Selection of Solver Configurations
上面提到，MIP求解器通常实现了多样化的求解技术、并提供了大量求解流程的控制配置，以应对不同类型问题的求解需求。然而，对于某个具体问题，求解器由于缺少先验信息，只能在求解过程中根据实际表现动态调整配置；这种做法不但在求解过程前期存在效率损失，而且不一定能在短时间内找到合理的求解配置。因此，即使通过调用求解器来解决MIP问题，我们也可以通过优化求解器配置来取得更好的效果。具体来说，
- 一方面，我们可以结合对问题结构和求解需求的理解来选择合适的求解器的配置。例如，对于可满足性问题(SAT)等主要关注可行性的问题，在node selection阶段选用dfs/be等关注可行解的方法要优于bfs等关注下界估计的方法。
- 另一方面，对于需要反复求解的任务，我们可以先设计一组小规模的测试问题对不同求解器配置的效果进行评估，然后选出效果较好的几组配置用于后续主求解流程中。
其他建模与求解技巧 Other Modeling and Solving Techniques
除了对求解器的配置进行优化，我们还可以基于对问题的理解，改进问题形式(formulation)，或者定制新的求解方式与求解器进行搭配：
- 通过理论分析，给出更强/理想的问题形式。例如，在描述受0-1变量控制的连续变量时，可尽量避免big-M的使用。
- 结合B&B流程的特点，调整问题形式以提高求解器的效率。例如，引入lift变量以改善branching步骤的算法效率。
- 启发式方法与求解器的结合。很多MIP问题背后有非常直观的业务逻辑，但相应的数学规划形式却比较复杂。根据个人经验，这类问题比较适合通过启发式方法来寻找解，然后通过求解器对启发式方法的效果进行校核。另外，注意到B&B等基于LP的方法属于外部逼近方法，而启发式搜索方法属于内部逼近方法，两种不同视角可能可以结合，形成更高效的求解方案。
MIP求解器的开发 How to develop an MIP solver?
基于某些原因，使用者可能需要从头开始实现一个MIP求解器。不过，正如上面所提到的，如果要满足市场所需的通用性，MIP求解器通常需要实现大量专门化的求解技术，这对于没有充分的资源和业务经验支持的个人或者小团队来说是十分困难的。因此，至少在开发前期阶段，开发者需要有一定的侧重点，专注于求解器的某几项核心功能。我个人认为一种较合理的开发思路是先以某一类业务问题为切入点，基于一套可扩展的框架实现核心求解逻辑；后续再逐步引入专门化功能，扩大求解器的应用面。
在实现核心求解逻辑时，开发者可以参考借鉴已有的开源工作，例如CBC、SCIP等，也可以参考我在本系列中的尝试。特别地，我认为有以下几个需要特别注意的工程设计问题：
- 数据结构设计：在求解器中，类和数据结构的形式对计算和存储性能有重要影响，而且一旦确定，后续修改成本很高。因此，有必要根据求解器的主要应用方向设计类和数据结构的形式。例如，在SCIP中，约束（行）与变量（列）被认为是不同的对象，有独立的数据结构和处理逻辑；这是因为在MIP问题中通常有大量包含组合结构的约束，通过独立的处理逻辑可以利用这些组合结构来提高branching和domain propagation的效率。但与此同时，这种数据结构形式将会为LP松弛问题的求解增加一定的计算开销，因为LP求解器通常需要将行和列作为同一类对象进行处理。由于SCIP在设计之初更多是为了解决SAT/CIP等与布尔逻辑判定相关的问题，而对于这类问题，LP求解模块的重要性相对更低，故对约束使用独立的数据结构管理是更合适的。
- 模块设计与可扩展性：随着新求解技术的不断引入，对技术的动态管理和控制会变得越来越复杂，很多地方需要加入具体求解技术选取的判断逻辑。此时，如果模块间的边界或者交互形式不清晰，前述判断逻辑可能较难实现或者容易出bug。例如，在本系列的实现中，约束相关信息没有专门的管理对象，而是在solver、propagator等多个类中都保存有独立备份；这导致后续较难对割生成技术进行支持，因为生成割平面后需要对问题约束信息进行改动，而这种改动在当前实现中是不可控的。