应用机器学习的分支定界算法求解混合整数线性规划问题

混合整数线性规划问题

给定一个矩阵 $A\in \mathbb{Q}^{m\times n}$, 向量$c\in\mathbb{Q}^n$ 和$b\in\mathbb{Q}^m$，一个集合$\{1,...,n\}$的划分 $(\mathcal{A}, \mathcal{B}, \mathcal{C})$ . 一个混合整数线性规划问题(Mixed Integer Linear Programming, MILP)的定义如下：

$$\begin{aligned} z^* = \min\ \ & c^T x \\ \text{subject to } & A x \geq b , \\ & x_{j}\in \mathbb{Z}_{\geq 0} \hspace{3mm} \forall j\in \mathcal{ A}, \\ & x_{j}\in \{0,1\}\hspace{3mm} \forall j\in \mathcal{B}, \\ & x_{j}\geq 0 \hspace{3mm} \forall j\in \mathcal{C}. \\ \end{aligned}$$

设$\mathcal{I}:=\mathcal{A}\cup \mathcal{B}$表示整数和二进制变量的集合。如果$\mathcal{A}=\emptyset$，则称混合整数线性规划为混合二进制；如果$\mathcal{A}=\mathcal{C}=\emptyset$，则称为二进制。去除限制$\mathcal{I}$，则得到一个线性规划（Linear Programming, LP），称为MILP的LP松弛。

MILP求解器

现代求解器解决MILP问题是使用了分支定界算法（Branch and Bound, B&B），这是一个精确求解算法。

B&B通过通过MLIP的LP松弛进行可行区域划分，进而解决更小的子MILP。这种划分方案可以表示为一棵搜索树，其中每个节点代表一个子MILP。在搜索过程中，整数可行解的目标函数值提供了$z^*$的上界。已知的最优上界值称为原始界（primal bound），用$\bar{z}$表示。同样，探索过的节点的LP松弛的解$z^{LP_i}$作为下界。设$\underline{z}:=\min_{i: i\text{ expored}} \{z^{LP_i}\}$提供了$z^*$的下界，称为对偶界（dual bound）。当所有节点都已处理完毕，或$\bar{z}=\underline{z}$，或符合其他终止条件（如超时）时，B&B算法结束。

这些是B&B算法在商业求解器（如CPLEX、Gurobi或Xpress）以及学术求解器（如SCIP）中实现的基本原理。在实践中，B&B算法的执行依赖一些关键求解组件，这些组件负责求解过程的不同方面，它们共同决定了求解一个MLIP问题的时间。最重要的组件是预处理、分支规则、割平面和原始启发式。

预处理。预处理指通过识别子结构等方式，移除冗余的、不必要的约束，从而减小问题规模。

分支规则。划分可行区域的过程称为分支。而分支规则一般包含两方面：节点选择和变量选择。关于选择什么节点、选择哪个变量作分支是需要决定的。选择节点指要考虑的未处理的B&B节点。而变量选择一般是使用单变量分支，其为

$$x_j \leq \lfloor x^{LP}_j \rfloor \lor x_j \geq \lceil x^{LP}_j \rceil\,,$$

对于某些$j\in\mathcal{I}$，使得$x^{LP}_j \notin \mathbb{Z}$，即对该子问题下的LP松弛解中不满足整数约束的变量进行上界或下界的收缩，将可行域切分，分成两个子问题。然而，LP松弛的解可能违反多个整数约束，这意味着有多个候选变量可以进行分支，需要从中选择一个。

割平面。割平面指通过添加线性不等式来收紧MILP的可行域，但不排除任何整数可行解。这可以在B&B树的任何可行域非空的节点中进行，不过在实践中一般在根节点使用割平面。而在根节点之外添加割平面的B&B过程通常称为分支切割（Branch and Cut）。但是割平面也可能会产生问题：虽然割平面的添加能够收缩可行域，但大量切割可能会减慢LP求解速度并导致数值不稳定。因此，审慎的割平面策略至关重要。

原始启发式。原始启发式来指尝试在短时间内找到可行解的方法。仅依靠分支定界来找到解通常效率比较低下。而原始启发式可以迅速找到一个可行解，从而有效地降低原始界$\bar{z}$。与割平面类似，原始启发式可以在树的任何节点中使用。

MILP的评估指标

如何评估求解器求解一个MILP问题的好坏，有一些量化的指标。首先定义时间变量$t\geq 0$。将原始界$\bar{z}(t):[0,T_{\max}]\mapsto \mathbb{R}$和对偶界$\underline{z}(t):[0,T_{\max}]\mapsto \mathbb{R}$定义为时间的函数。我们定义如果在时间$t$尚未找到整数可行解，则$\bar{z}(t)$为无穷大。设$\epsilon = 10^{-6}$，用于一些被$0$除的情况。注意有些指标需要用到最优解的目标函数值$z^*$，因此一些指标必须在问题解决后计算。

最优间隙（Optimality gap）

g(t) := \begin{cases*} \infty & 如果尚未找到解或$\bar{z}(t)\cdot \underline{z}(t)<0$,\\ \frac{|\bar{z}(t)-\underline{z}(t)|}{\min \{|\bar{z}(t)|, |\underline{z}(t)|\}} & 否则。 \end{cases*}

或者，也可以设为$g'(t)=|z^*-\underline{z}(t)|$。

原始间隙和积分

对于给定的可行解$x$，我们定义原始间隙$\gamma(x)$为

\gamma(x) := \begin{cases*} 1 & 如果$z^*\cdot c^Tx < 0$, \\ \frac{|z^*-c^Tx|}{\max\{ |z^*|,|c^Tx|, \epsilon \}} & 否则。 \end{cases*}

我们可以定义一个原始间隙函数，将求解时间映射到到目前为止找到的最佳解的原始间隙。特别地，记$x(t)$为时间$t$找到的最佳解，我们定义

p(t) := \begin{cases*} 1 & 如果在时间$t$尚未找到解,\\ \gamma(x(t)) & 否则。 \end{cases*}

原始积分定义为

$$P(t_{\max}) := \int_0^{t_{\max}} p(t) dt.$$

原始对偶积分

可以扩展原始积分的概念以考虑对偶界的改进。为此，我们使用最优间隙代替原始间隙，并积分函数

pd(t) := \begin{cases*} 1 & 如果尚未找到解或$\bar{z}(t)\cdot \underline{z}(t)<0$,\\ g(t) & 否则为上面的g(t), \end{cases*}

得到原始对偶积分，定义为

$$PD(t_{\max}) := \int_0^{t_{\max}} pd(t) dt.$$

搜索树大小

B&B树的节点数量在一定程度上反映了求解时间，因此节点数越小，意味着求解时间更短。

机器学习的部件

原始启发式

原始启发式算法的作用是快速找到可行解，因而改善原始界 $\bar{z}$ ，从而能够剪枝更多的节点，特别是在求解初期阶段，能够加快求解。而机器学习技术可以利用实例中的共性结构，快速找到一些可行解而因此备受关注。为此，已经提出了多种方法。从概念上讲，这些方法可以分为三大类：

1. 预测解以引导搜索
2. 学习解的邻域搜索改进解
3. 学习调用已有的原始启发式方法

根据方式是否需要一个可行解，将原始启发式算法分为两组。

• 需要一个可行解，其目标是对其进行改进，称之为改进启发式算法。

• 不需要一个可行解，称之为起始启发式算法

  这些算法可以在树的任何一个节点中运行。改进启发式算法的一个典型例子是大邻域搜索（LNS）。

预测解以引导搜索

预测解以引导搜索指的是，对于一个MILP问题中的二元变量，通过机器学习来识别在最优解里，它们取$01$的概率，得到预测后，就可以交给MILP求解其余变量，从而缩小问题的规模。这一般被称为温启动。

如何进行学习呢？这可以被视为一个监督学习任务，其中期望输出是最优解的值。然而，用于训练阶段的标签的最优解的求解代价往往比较高昂，因此退而用可行解来学习预测。即，学习过程从一个数据收集阶段开始，对每个问题实例 $X$，收集一组可行解 $D(X) = \{\hat{x}^{(1)},\hat{x}^{(2)},..., \hat{x}^{(K)}\}$。目标是学习一个函数 $p_\theta (x_j=1|X)$，其参数为 $\theta$，可以解释为给定问题 $X$ 时变量 $x_j$ 取值为1的概率。参数被调整以使这些函数的行为尽可能接近目标概率分布 $p_T (x_j=1|X)$ 的行为。 具体可参考以下文章：

• Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction
• MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers
• Solving Mixed Integer Programs Using Neural Networks

学习解的邻域搜索改进解

解的邻域搜索指的是，给定一个初始可行解 $\hat{x}$，选择要固定的变量值，优化其他变量，即探索其邻域。这一过程可以反复运行。该方法同样期望能识别出问题的子结构，以将其分解为更小、更易处理的子问题。在这种方法中，学习的目标不是预测变量在最优解中的取值，而是预测变量在当前最佳解 $\hat{x}$ 中是否已分配到其最优值。具体可参考以下文章：

• A General Large Neighborhood Search Framework for Solving Integer Linear Programs
• Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs
• Learning Large Neighborhood Search Policy for Integer Programming
• Learning to Search in Local Branching
• Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning

学习调用已有的原始启发式方法

目前的MILP原始启发式算法非常丰富，有实验表明，没有单一的启发式算法适应所有的问题，其优化程度高度依赖于问题，甚至依赖于求解阶段。因此，还有一种优化思路是如何利用这些原始启发式方法。即在一组原始启发式算法中，此时应该运行哪一个？

学习的方法是观察所选启发式算法的性能。这个简单的方法包含了经典的利用与探索的权衡：在已知的表现良好的启发式算法和运行性能未知的启发式算法之间找到平衡。

除了决定运行哪些启发式算法以及运行多长时间，还有“何时”运行它们的问题，即在哪些B&B的节点上运行。

• Learning to Run Heuristics in Tree Search
• Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms
• Adaptive large neighborhood search for mixed integer programming
• Online Learning for Scheduling MIP Heuristics
• Learning to Schedule Heuristics in Branch-and-Bound

未来展望

上述讨论的优化方法，大都是在特定类别的MILP问题内进行学习，而泛化到其他问题来说是比较困难的。这在某方面使得机器学习的原始启发式算法集成到MILP求解器带来困难。 不过有研究表明，与强化学习结合的探索解空间的算法在一定程度上的泛化是可行的。

通过组合现有的原始启发式算法来创建新的强大启发式算法也是一个热门的方向。其本质的多臂赌博机问题，已经取得了一些成功。然而，为了能往正确的方向优化，获得更高的性能，需要对性能预测有更高的认识，并需要能有一定的问题泛化能力。

分支规则

分支是B&B算法的关键步骤。在已提出的的分支规则中，强分支（Strong branching）会产生较小的B&B树，但每个分支的计算成本很高。还有一个被称为伪成本（pseudocosts）规则据过去的值来估计。有一种说法是在树的根节点附近执行强分支，然后在变量分支足够多次后切换到使用伪成本，因为初始化阶段的分支对整棵树的大小影响巨大。

分支规则的目标都是最小化求解时间。但求解时间包括计算时间、节点数量等等，这可能需要在不同计算部分之间取得平衡。

学习强分支

关于强分支规则的近似是最早进行的。在早期的分析得知，在分支决策影响最大的根节点执行强分支是非常有利的，其次，一个有希望的改进方向是适应问题结构。

对于强分支规则的近似任务，这可以视为一个预测任务，即根据变量特征预测变量的强分支分数，但也可视为一个排名。不需要知道它们的具体分数，而是预测出其相对大小。

而从变量特征到变量分数的映射，除了最早的自定义特征外，2019年提出的GNN模型被证明在变量选择中非常有效，他们通过行为克隆的方式训练GNN来模仿强分支，但此时的方向仍是针对同一类问题的求解能力评估。

• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Exact Combinatorial Optimization with Temporo-Attentional Graph Neural Networks
• Learning to Branch in Mixed Integer Programming
• Lookback for Learning to Branch
• Hybrid Models for Learning to Branch
• A Machine Learning-Based Approximation of Strong Branching

学习通用分支规则

上述讨论的方法都仅仅在特定的MILP类问题进行学习和应用，但应用到其他类的MILP问题则效果不好。为了学习到一个通用策略，一个研究方向是在变量选择中增加搜索树的信息来克服它。这个方向的假设是，在MILP之间，存在一种更高阶的信息，并且这种信息可以在B&B树的空间中被捕获。

尽管如此，如何利用B&B树的信息，仍待研究。

• Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies
• Learning to branch with Tree-aware Branching Transformers

不依赖于专家的分支学习

与其他分支策略相比，强分支生成的B&B树相对较小，因此先前的模仿学习模仿的策略都是强分支策略。但是由于一些原因，比如：强分支的标准实现依赖于一些计算过程中的额外数据，比如上下界收缩以及其他统计数据，而单纯的模仿学习并没有依赖这些数据，因此进行完美的模仿，其性能也会比预期差。而在没有比强分支更好的替代方案的情况下，能否不依赖专家知识进行分支规则的学习？

有研究证明，当使用深度优先搜索（DFS）的选择节点规则进行节点遍历时，最小化每个子树的大小相当于最小化整个B&B树的大小。除此之外，有研究在此基础上定义了一个新的学习分支框架，称之为树MDP。树MDP与一般的MDP之间的区别，在于其行为影响的范围仅仅是这棵子树内，而不是后继的整个状态。

还有的研究设法将树剖成链，让网络学习一条条链。

实验表明，在强分支表现非常好的实例上，模仿学习的方法更优。然而，当强分支表现不佳时，基于RL的方法能够找到更好的分支策略，体现了在某些情况下无专家学习的潜力。

• Reinforcement learning for variable selection in a branch and bound algorithm

• Learning to branch with tree MDPs

• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories

生成分支规则

与直接学习分支规则不同，有工作致力于学习如何生成一个分支规则，通过强化学习的方式，用四则运算、预设常数和预设的函数来生成小型函数，并通过实验表明运行在纯CPU基础策略在性能上与先前的GPU基础的最先进方法相当。

• Rethinking Branching on Exact Combinatorial Optimization Solver: The First Deep Symbolic Discovery Framework

强化学习和模仿学习的结合

有工作将强化学习和模仿学习相结合，提出的混合代理以迭代方式执行，在线RL代理决定样本生成，而离线RL代理进一步筛选具有高累积回报的生成样本。在不同的MIP问题上的实验表明了该方法的有效性，甚至在某些情况下超过了领先的商业求解器。

• Towards Imitation Learning to Branch for MIP: A Hybrid Reinforcement Learning based Sample Augmentation Approach

未来展望

适应性

上述的工作都表明，没有单一的分支规则在所有问题中都表现优异。而最终目的是希望有一种分支规则，该分支规则能够动态适应各类问题的具体特征。一种引入这种适应性的方法是控制模型用于学习的数据样本的分布。虽然已有研究致力于分支规则的适应性，但如何使用或在不牺牲速度的情况下进一步提高性能的方式，还需探索。

专家指导

许多工作都使用强分支规则作为学习有效决策的专家。然而对强分支学习的有效性有些许质疑，一些例子表明，强分支评分未能提供有用的信息。值得研究的方向包括寻找新的专家，更好地模仿它们的新策略，或者相反，在没有专家知识的情况下进行学习。这显然需要强化学习的方法。

新的方向

除了上述方向外，还有许多较少研究的方向，比如，强调重要变量的子集而不是在每个节点选择单个变量，该重要变量的子集指的是，在分支定界过程中，只通过在这个后门上的变量进行分支，就可以解决实例达到全局最优或证明其不可行。有工作提出了一种找到这种重要子集的方法，并展示了将它们用作优先分支候选者的潜力。

• Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework

割平面

割平面程序是现代MILP求解器的另一个重要部分。给定一个LP松弛解$x^{LP}$，将生成若干不同类别的割平面，通过选择规则选择其中的一个子集，添加它们并重新求解LP松弛解。一个好的选择标准对于改进LP松弛至关重要，但要避免过多的割平面导致减慢LP求解并导致数值不稳定。因此，如何选择有效的割平面成为了学习的方向，而不是生成割平面。

最近的研究中，割平面通常在根节点应用得更多，虽然在其他节点进行割平面没有问题，但尚不清楚在根节点之外使用割平面在计算上是否有益。

单割平面选择

早些研究将割平面选择任务建模成MDP。在每一步$k$，从割平面池$\mathcal{C}_k$中选择一个割平面$c_k$，然后重新求解LP松弛。具体来说，设$\mathcal{C}$是一组割平面，$z(\mathcal{C})$是添加所有割平面$\mathcal{C}$后求解LP松弛的结果。度量是第$k$步割平面$c$所带来的LP界限改进，定义为

$$\Delta_k(c):=z\left(\{c_1,...,c_{k-1},c\} \right) - z\left(\{c_1,...,c_{k-1}\} \right) \, .$$

为简单表示，设$z_k=z\left(\{c_1,...,c_{k}\} \right)$。

有一研究采用模仿学习，魔方一个显示的贪心策略：每次从割平面池$\mathcal{C}_k$中选择一个割平面$c$，其$\Delta_k(c)$最大。他们的计算研究表明，与其他选择规则相比，这种模仿贪心方法在添加$T$个割平面后，其LP界限的改进非常有效。

还有研究使用强化学习，设定奖励为$R_k=\Delta_k(c_k)$。但是样本效率低且缺乏泛化能力。

• Learning to cut by looking ahead: Cutting plane selection via imitation learning

• Reinforcement learning for integer programming: Learning to cut

多割平面选择

上述方法仅仅是将选择割平面分成$T$个步骤，然而事实上，不同割平面之间会有相互影响，而上述方法忽略了这个内在关系。

• Adaptive Cut Selection in Mixed-Integer Linear Programming
• Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model

选择之外

除了选择割平面之外，还有可作的决策，比如添加的割平面数量。

未来展望

衡量性能

多割平面轮次

节点选择

原始启发式的目标是改善原始界限，而分支规则和割平面旨在改善对偶界限。节点选择策略则是在于平衡这两个目标。通常，更好的节点选择规则能带来更短的求解时间，因为这能得到一个较小的搜索树。为此，需要避免处理一些可被修剪的节点，比如松弛解比最优解还差的节点。

一种节点选择策略是选择最佳对偶界限的节点。这称为最佳优先搜索（Best First Search，BFS），其优点是能快速改善对偶界限。另外一种节点选择策略是深度优先搜索（Depth First Search，DFS）策略，它优先处理最新分支的节点，类似于原始启发式，旨在快速找到可行解。

有研究提出一种策略，该策略选择处理通向最优解路径上的节点。这需要在训练过程中知道最优解，从而得知哪条路径通向最优解。还有研究学习一个函数，该函数可以比较树中的任何两个节点的优劣。

• Learning to Search in Branch-and-Bound Algorithms
• Learning to Compare Nodes in Branch and Bound with Graph Neural Networks
• A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP
• Reinforcement Learning for Node Selection in Branch-and-Bound

未来展望

上述论文的实验结果虽然有所改进，但改进的幅度很小。一般来说，一个有效的原始启发式和分支策略更为重要，而节点选择策略的影响相对较小。

求解配置

MILP求解器可调整的参数非常多。比如SCIP 8版本中，它有超过$2000$个用户可调参数。而适用于不同问题的参数可能不唯一。因此，可以通过机器学习来预测某些参数。

• Learning to Configure Separators in Branch-and-Cut

MILP的嵌入

给定 $A\in \mathbb{Q}^{m\times n}$，$c\in\mathbb{Q}^n$，$b\in\mathbb{Q}^m$ 以及变量的划分 $(\mathcal{A}, \mathcal{B}, \mathcal{C})$，MILP求解器就可以求解。上述提到的机器学习方法都是将{$A$, $c$, $b$} 作为输入。可如何输入呢？我们希望有一些性质。

1. 置换不变性： 交换变量或约束的顺序不应改变此问题。
2. 尺度不变性：尺度不变性是为了将数值保持在可控范围内，这有助于学习过程。这可以通过归一化步骤实现。
3. 大小不变性：表示的大小不应取决于实例的大小。即，我们需要每个需要表示的元素（例如，每个变量或每个节点）的固定大小描述。
4. 低计算成本：数据的提取、存储和处理成本低。