在这篇文章中，我将回顾割(cut)方法的基本思路，介绍将其引入B&B求解流程中的常用手段及注意事项，并实现最基础的基于线性约束的变量边界加强(bound tightening/domain propagation)方法。
割方法简介 Introduction of Cut Methods
在将混合整数规划(MIP)问题放松为线性规划(LP)问题求解时，LP求解结果对MIP结果的估计准确程度取决于MIP问题形式(formulation)的“规整”程度(integrality)：不妨假设在当前问题形式下，MIP问题的可行域是$P_I$，而LP松弛问题的可行域是$P$，那么当多面体$conv(P_I)$与$P$之间的差距越小时，LP松弛问题求得的解越接近整数可行解，问题形式的规整性越高。特别地，如果$P = conv(P_I)$，那么根据线性规划的几何性质，LP最优解$x_{LP}^* \in ext(P_I) \subseteq P_I$也是MIP问题的最优解。（关于MIP问题形式的规整程度的更多相关讨论可以参考我之前这篇blog post。）
割平面(cutting planes/cuts)是一类线性约束，这种约束试图在保持MIP可行域$P_I$中所有解可行的情况下，切割掉LP可行域$P$的一部分解（特别是LP松弛问题对应的最优解），以降低多面体$conv(P_I)$与$P$之间的差距、提高问题形式的规整性。在最理想情况下，我们可以通过在问题形式中添加割平面使得$P = conv(P_I)$，此时只需求解一次LP松弛问题即可完成对MIP问题的求解，无需调用B&B流程。
割方法对许多MIP问题的理论分析和求解算法设计提供了重要基础。特别地，对于很多MIP问题，我们可以通过组合理论系统性地引入割平面（例如Sherali-Adams Hierarchy）以获取更强的问题形式、甚至是理想问题形式$P = conv(P_I)$；虽然这通常需要引入指数多个割约束，但是其好处在于结构清晰，可以对多种近似求解方案在统一的理论框架下进行分析。并且，在实际求解过程中，含有指数多个约束的问题不一定是计算上不可行(intractable)的：我们可以利用分解(decomposition)以及惰性约束(lazy constriants)等计算技巧来提高计算效率。
B&B流程中的割生成方法 Cut Generation in B&B Procedure
在这一小节中，我将介绍在B&B流程引入割生成方法的常规思路。
首先，通用方法生成的割平面虽然能很好地改进问题形式的规整性，但是这类割往往只能作为新增约束添加到已有问题形式中。由于LP的主要求解算法——单纯形法——的核心计算通过线性方程求解实现，而线性方程求解依赖于约束矩阵的分解（例如，LU分解）提高计算效率，故当生成新的割平面/约束时，约束结构发生变动触发约束矩阵分解的更新，进而对LP求解效率产生负面影响。（思考题：能否根据具体的割生成方法，定制化更高效的矩阵分解的计算和更新方法？）因此，为保证计算效率，通常只在B&B流程中的一些关键节点（例如，求解根结点问题时）考虑加入通用方法生成的割平面。
然而，从另一个角度，B&B流程本身可以看成是一种特殊形式的割生成流程：在每一步迭代中，我们对某个子问题的某个变量的上下界约束进行加强，然后重新求解子问题。由于在单纯形法的求解过程中，变量上下界变化的影响很小（求解流程可以直接基于已有的基和解进行迭代），因此B&B流程相比通用的割生成流程更适合与单纯形法（或者其他LP求解算法）结合。基于这一认知，我们可以进一步在B&B流程中考虑branching以外的对变量上下界进行加强(bound tightening)的方法。一类较为通用的加强变量上下界约束的思路被称为**可行域传播(domain propagation)**：这种方式尝试根据branching后变量上下界的改动推断其他变量上下界的变动情况。由于这种方法依然只改变了变量的上下界，因此不会明显影响B&B流程中的LP求解效率。不过，这种方法相比一般的割生成方法的缺点在于算法效率（即改进问题形式的规整性）低：它只能沿着坐标轴方向对问题的可行域进行切割，导致当原MIP问题和LP松弛问题的可行域差异主要处于坐标轴的斜角方向时，需要进行多次branching+变量上下界加强才能实现单个普通割平面的效果。例如，在T. Ahterberg的博士论文中曾介绍过这样一个例子：对于可行域
$$\{(x,y)|0.2 \leq x-y \leq 0.8, \ x,y \in \{0,\cdots,1000\}\},$$
如果通过domain propagation，将需要接近1000次迭代才能证明该约束下无解；而利用一般的割方法则可以直接判断该可行域为空。
上述关于算法效率和计算效率的权衡可以进一步推广到对不同形式的割平面的选取中。例如，在B&B流程中加入具有稀疏结构或组合结构的割平面约束通常效果更好，因为这些约束对LP求解中的矩阵相关计算的效率影响更少，同时也可以更高效率地与domain propagation进行结合。具体来说，对于常见于big-M等建模方法中的variable bound约束，虽然在domain propagation中处理逻辑与普通的线性约束并无明显区别，但是由于约束稀疏（约束中包含的变量数只有2个）且变量系数形式简单（有一个变量的系数为1），因此需要的计算量显著更少。又如，由于knapsack约束中系数都是整数且变量的取值都为0-1，因此可以通过排序等方式做domain propagation，在节省了计算量的同时达到了更高的计算准确度。
对线性约束的边界加强方法 Domain Propagation for Linear Constraints
这一小节中，我将简单介绍domain propagation中线性约束的处理方法。在后续代码实现中，我将实现该方法，并通过测试案例检验其效果。
首先，不妨假设变量$x$的上下界为$[l,u]$。我们定义一个线性约束$b_{l,i} \leq a_i^T x \leq b_{u,i}$的隐含上下界(implied bounds)为
$$b_{l,i}^{im} = \min_{l \leq x \leq u} a_i^T x, \ b_{u,i}^{im} = \max_{l \leq x \leq u} a_i^T x.$$
根据上述定义，对于每个满足系数$a_{ij} > 0$的变量$x_j$，我们可以推断其下界$l_j$应不小于
$$l_j^{im} = (b_{l,i} - \max_{x_{-j}} a_{i,-j}^T x_{-j}) / a_{ij} = (b_{l,i} - b_{u,i}^{im}) / a_{ij} + u_j,$$
且其上界$u_j$应不大于
$$u_j^{im} = (b_{u,i} - \min_{x_{-j}} a_{i,-j}^T x_{-j}) / a_{ij} = (b_{u,i} - b_{l,i}^{im}) / a_{ij} + l_j;$$
上述变量被称为变量$x_j$的隐含上下界。同理，可推得系数满足$a_{ij} < 0$的变量$x_j$的隐含上下界$l_j^{im},u_j^{im}$。
现在，当一个变量$x_j$的上下界发生变化$[l_j,u_j] \to [l_j’,u_j’]$时，我们可根据上述方法，计算这一变化通过每个约束$b_{l,i} \leq a_i^T x \leq b_{u,i}$传递到另一个变量$x_{j’}$上的隐含上下界$l_{ij’}^{im},u_{ij’}^{im}$；如果存在其中一个隐含上下界比当前上下界$l_{j’},u_{j’}$更强，我们就可以更新该变量的上下界约束。上述流程可以不断重复，直至没有变量可以获得更强的上下界约束为止。
建模技巧 Modeling Tricks
上述讨论的另一个重要意义(implication)是：我们可以在MIP问题的建模过程中利用B&B流程和割生成方法的理论和计算特性，设计更好的问题形式来提高求解速度。下面举两个简单的例子：
- lifting: 在上面提到的例子$\{(x,y)|0.2 \leq x-y \leq 0.8, \ x,y \in \{0,\cdots,1000\}\}$中，我们可以引入新的整数变量$z = x - y \in Z$，以在$x-y$方向上进行branching和domain propagation。容易看出，在引入lift变量后，上述问题可以直接通过B&B流程快速求解，无需引入新的割生成流程。
- encoding: 对SOS1约束$\sum_j x_j = 1$，原始的branching会产生（深度上）很不平衡的B&B树：$x_j = 1$仅对应其他所有$x_{j’}$都为0这一种情况，而$x_j = 0$则可能对应多种情况。我们可以通过lift变量将这种约束编码为一组约束，使得branching+domain propagation在这组约束下能产生更平衡的B&B树，从而提高B&B流程的求解效率。例如，我们可以将约束$x_1 + \cdots + x_4 = 1$编码为$x_1 + x_2 = y_1, \ x_3 + x_4 = y_2, \ y_1 + y_2 = 1$；此时，每个变量$y$的两个branching分支是平衡的：各分支都恰好对应两种$x$的取值情况。（关于MIP建模中encoding技巧的更多相关讨论可以参考我之前的一篇blog post。）