机器学习求解混合整数规划综述：从分支定界到学习型启发式

MIP 问题相关定义

MIP 问题

如果一个问题包含没有二次项的目标函数，且目标函数和所有的约束条件都是线性的，且至少有一个整数决策变量，则问题可被定义为 MILP (Mixed Integer Linear Programming)问题：

min\ c^Tx \newline s,t \ Ax \geq b, x \in \mathbb{R}^n, x_{j} \in \mathbb{Z}, ∀j \in I

举一个案例：高中时期学习的线性规划，是连续的，考虑：

\max 3x +2y \newline x + y \leq 4 \newline x\geq 0 \newline y \geq 0

一般的求解过程是先画出可行域，然后使目标函数在可行域中的取值最大。但是情况换成混合整数时，求解的过程和线性的过程就不一样了：

\begin{aligned} \max\quad &3x+2y\\ \text{s.t.}\quad &2x+2y\leq 3\\ &x,y\in\{0,1\} \end{aligned}

这里的 $x$ 和 $y$ 只能从 0 和 1 中选择，可以采用暴力枚举的方式，最终得到的结果和在连续情况下线性规划求解的值是不一样的。随着变量数量的增加和可选取值的增加，会导致组合爆炸问题，因此 MILP 问题是一个 NP-hard 的问题。

通过求解 MILP 相应的 LP 松弛（即去除掉取值必须为整数的约束），能够给出 MILP 最优解的一个下界：

\min c^Tx \newline s.t. Ax \geq b, x \in \mathbb{R}^n

当今主流的解决 MIP 问题的方案只要有基于分支定界的精确求解算法和基于启发式的近似求解算法。

类MIP 问题

在 MILP 问题的基础上，如果至少有一个二次项的在目标函数中，问题就变成了混合整数二次规划（Mixed Integer Quadratic Program）。如果模型中的限定条件中包含二次项，则问题定义为混合整数二次约束规划，本文暂不讨论。

Branch-and-bound（B&B）

分支定界（Branch-and-bound）是一种经典的树搜索算法，通过分治算法，对变量值进行分支来划分搜索空间，使用问题松弛的边界来从树中剪枝没有前途的区域。以上图为例，下图给出了了具体的算法执行过程：

算法首先通过线性规划松弛获得原问题最优值的下界，然后选择不满足整数约束的变量进行分支，将原问题递归划分为若干子问题。在搜索的过程中，算法通过求解各子问题的线性松弛来计算下界，同时利用已找到整数可行解更新全局上界。对于不可行、已经得到了整数的最优解或者不可能改善当前最优解的节点，则进行剪枝操作提前终止其搜索，当所有必要的子问题都已经执行完毕或者全局上下界收敛到相同的值时，算法终止，并且给出具有全局最优保证的整数解。 B&B 算法最大的问题是其搜索树可能会呈指数级别的增长，例如一个 MILP 问题包含大量的整数变量，每次分支都会产生两个子节点：

T(n) = 2T(n-1)

在最坏的情况下，搜索树可能会达到 $O(2^n)$ 级别的计算量，使用一个 B&B 问题求解复杂 MLIP 问题，可能需要执行数百万次分支变量选择。

Branching Variable Selection（BVS）

分支变量选择会产生不同的子问题，进而影响整个搜索树的结构。好的分支变量能够帮助快速剪枝，而不合适的变量可能会导致大量不必要的搜索。BVS 的目标就是尽可能选择能够提高后续搜索效率的变量。为了衡量每个候选分支变量的质量，使用该变量的得分来衡量其有效性，并且挑选其中得分最高的候选变量进行分支。BVS 中衡量质量的评分方法主要有以下三种：强分支（strong branching, SB）、伪成本分支（Pseudo-cost Branching）、混合分支（Hybrid Branching）。

强分支

基本思想是提前尝试候选变量的分支，评估分支后的效果，再去决定真正使用哪个变量。例如一个候选变量为：

C = \{x_{1},x_{2},x_{3}\}

强分支会分别尝试对这些变量进行分支，并且评估产生的两个子问题，可以通过求解或部分求解子节点的线性规划松弛来衡量分支对于目标界限的改善程度，但这也同时引入了额外的计算开销。为了解决这个问题，可以通过训练一个机器学习模型来模仿 Strong Branching，例如通过学习一个函数：

f_{\theta}(s,x_{i}) \rightarrow \hat{s}_{i}

其中：

$s$ ：当前 MLIP 子问题及搜索状态。
$x_{i}$ ：候选分支变量。
$\hat{s}_{i}$ ：模型预测的分支评分。
$\theta$ ：机器学习模型的参数。

可以通过模型来预测 $x^* = \arg\underset{x_i \in C}\max f_{\theta}(s, x_i)$ 。以此避免每次分支时对全部候选变量来执行强分支评估。 Khalil et al. (2016)提出了在前 500 次分支使用传统强分支，同时收集训练数据，从第 501 次分支开始，改用学习得到的模型进行决策，但该方法需要大量人工设计的特征，特征计算本身也会产生较大的开销。 Gasse et al. (2019)提出将 MILP 表示为二部图，然后使用图神经网络来学习变量与约束之间的关系。

二部图是一种特殊的图结构：将所有节点划分为两个集合，并且每条边都连接两个不同集合中的节点，在 MILP 中，第一个集合是变量节点：

V_{x}=\{x_{1},x_{2},x_{3}\}

第二个集合是约束节点：

V_{c}=\{c_{1},c_{2},c_{3}\}

如果是某个变量出现在某条约束中，就在它们之间建立一条边，每条边还可以记录变量在约束中的系数。通过 GNN 的消息传递机制，模型可以综合变量与约束之间的关联，来学习适合分支决策的特征表示。前面两种方法都依赖传统算法来提供高质量的决策作为训练目标，Etheve et al. (2020)尝试使用强化学习来直接训练 BVS 策略。基本的框架如下：

\textbf{当前求解状态} \rightarrow \textbf{选择分支变量} \rightarrow \textbf{执行分支}\rightarrow \textbf{获得反馈}

机器学习模型不断与 MILP 求解环境交互逐渐学习更加有效的分支策略。 Sun et al. (2020) 将分支变量选择建模为马尔可夫决策过程，使用强化学习相关方法来进行策略优化。

伪成本分支（补充）

伪成本分支的出发点是之前已经分支过一些变量，那么就可以利用历史记录预测其未来的分支效果，而不是每次都重新计算，类似于一种基于经验的分支预测。例如在先前的计算过程中可能发现历史上对 $x_{1}$ 分支能够显著提高 LP 下界，而对 $x_{2}$ 分支则对 LP 下界的改善较小，在下一次遇到这两个变量时，就可以优先考虑 $x_{1}$ 。伪成本衡量的是某个变量在一个分支方向上，每单位变量取值变化所带来的 LP 目标下界改善量。对于最小化 MILP： $\min c^T x$ ，设当前节点的 LP 最优值为 $z_{P}$ ，假设某个整数变量当前的 LP 解为 $x^*_{i}=2.4$ ，对应的 LP 最优值为 10，我们可以创建两个子节点：

向下分支： $x_{i}\leq 2$
向上分支： $x_{i} \geq 3$

假设求解两个子节点的 LP 松弛后，得到 $z_{down} = 11.2$ 、 $z_{up}=13$ ，由于父节点的最优值为 10,因此向下分支的下界改善量，及其对应的变化幅度：

\Delta_i^-=11.2-10=1.2 \newline d_i^-=2.4-2=0.4

向上分支的下界改善量，及其对应的变化幅度：

\Delta_i^+=13-10=3 \newline d_i^+=3-2.4=0.6

对应的单位变化成本很容易求得分别为 3 和 5，这些观测值会成为求解器维护伪成本统计信息的依据。随着 B&B 搜索进行，可以对不同分支的历史单位改善量取平均，求解器不断获得新观测，并且更新这些统计值。在分支决策阶段，假设得到的松弛解为 $x_{1}=3.7$ 、 $x_{2}=4.5$ ，历史统计信息为：

变量	向下伪成本 $PC_i^-$	向上伪成本 $PC_i^+$
$x_1$	3	5
$x_2$	4	4

首先计算每个变量的分数部分：

d_1^-=0.7,\qquad d_1^+=0.3

d_2^-=0.5,\qquad d_2^+=0.5

然后使用历史伪成本预测本次分支的下界改善：

\boxed{ \widehat{\Delta}_i^-=PC_i^-\cdot d_i^- } \newline \boxed{ \widehat{\Delta}_i^+=PC_i^+\cdot d_i^+ }

可以得到：

变量	预计向下改善	预计向上改善
$x_1$	2.1	1.5
$x_2$	2.0	2.0

接下来将两个分支方向的预测效果合并为一个评分，一种常见的方式是使用乘积：

\boxed{ s_i=\widehat{\Delta}_i^-\widehat{\Delta}_i^+ }

得到两个评分分别为 3.15 和 4，最终选择 $x_{2}$ 进行分支。乘积评分之所以有意义，是因为希望两个方向都具有较好的下界改善效果。实际的求解器还有可能使用包含最小值、最大值或者其它权重的评分函数，不统一采用纯乘积。伪成本分支的弊端在于，由于其需要利用历史信息，搜索刚开始的时候会遇到冷启动问题；同时历史估计还可能存在误差：同一个变量在不同的搜索节点中，可能遇到不同约束和变量界限的影响；以及归因不完全准确，求解器观测到的目标值变化，可能会受到约束传播、割平面和其它变量界限的共同影响，伪成本统计通常会将观测到的改善归因于记录的分支操作。

混合分支（补充）

在解释 Hybrid Branching 之前，有一个非常重要的过渡算法：Reliability Branching（可靠性分支）。强分支的特点是分支决策质量通常较高，计算成本昂贵但不依赖历史分支记录；而伪成本分支的特点是使用历史数据进行预测，计算的成本较低且搜索初期缺乏可靠的历史信息。可靠性分支的核心思想就是结合这两种方法：当伪成本尚不可靠的时候，使用强分支；当伪成本已经足够可靠时，使用伪成本预测。例如对于某个变量 $x_{i}$ ，维护 $N_{i}^-$ 和 $N_{i}^+$ 分别记录向下和向上分支的有效观测次数，通过设置一个可靠性阈值 $k$ ，当 $\min(N_{i}^-,N_{i}^+) \geq k$ 时说明两个方向都已经积累了一定数量的历史数据，此时可以认为伪成本相对可靠，否则需要进一步通过强分支获取信息。这个策略有效解决了伪成本分支的冷启动问题，同时避免了长期依赖昂贵的强分支计算。但这依然存在一个问题：无论是强分支还是伪成本，它们主要关注的都是分支对 LP 目标下界的改善。考虑以下案例，假设一个 MILP 包含：

x_{1},x_{2},x_{3},x_{4},x_{5}

我们准备在 $x_{1}$ 和 $x_{2}$ 之间选择分支变量。伪成本预测的结果如下：

变量	预计 LP 下界改善评分
$x_1$	8
$x_2$	6

按照伪成本分支应该选择 $x_{1}$ ，因为其预计能够带来更大的 LP 下界改善，但是假设发现，如果对 $x_{2}$ 分支，由于约束之间的关联，求解器能够进一步推断： $x_{3}=0、x_{4}=1、x_{5}=0$ ，其它三个变量的取值也被确定下来，这样一来子问题的搜索空间就会显著缩小。先前的方法只考虑了 LP 下界改善，并不一定能够完整反映它对 B&B 搜索效率的影响。 Hybrid Branching 希望同时考虑分支对 LP 下界的改善、分支能够触发多少约束传播、分支是否经常参与冲突、分支是否容易导致子问题被剪枝。 Hybrid Branching 通常使用以下评价指标：

伪成本：衡量变量分支对 LP 下界的预计改善。
推断值：衡量分支后预计能够推导出多少其他变量的界限收紧。
冲突值：衡量变量在冲突分析中的重要程度。
冲突长度：衡量变量参与的冲突约束的长度信息。
剪枝值：分支导致子问题被剪枝的历史表现。

推断值是 Hybrid Branching 单纯伪成本分支的重要区别之一，其指的是约束传播产生的推断。例如三个二进制变量 $x_{1},x_{2},x_{3} \in \{0,1\}$ ，并且存在约束 $x_{1}+x_{2} \leq 1$ 和 $x_{1}+x_{3} \leq 1$ ，现在假设决定 $x_{1}=1$ ，那么根据两条约束可以得到另外两个变量的值，只对一个变量 $x_{1}$ 做出决策，却顺便决定了另外两个变量。如果一个变量经常能够触发大量约束传播，就可能是值得优先选择的分支变量。对于冲突值，假设有以下约束 $x_{1}+x_{2}\leq 1$ ，其中 $x_{1},x_{2} \in \{0,1\}$ ，如果搜索过程中做出了 $x_{1}=1,x_{2}=1$ ，那么此时就和约束产生了冲突。求解器可以分析造成不可行性的原因，并且利用这些信息避免以后重复进入类似的不可行搜索区域。如果某个变量频繁参与近期产生的冲突，那么这个变量可能对问题的可行性结构具有较大影响，可以赋予其更高的优先级。冲突长度与冲突值相关，假设冲突分析得到了两条冲突约束，第一条涉及 $x_{1},x_{2}$ ，第二条涉及 $x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}$ ，第一条冲突约束只涉及两个变量而第二条涉及六个变量，通常较短的冲突约束能够提供更有针对性的限制信息。除了关注变量参与冲突的频率，还可以考虑它参与的冲突约束长度。剪枝值关注的是历史上对某个变量进行分支后，相关子问题有多大程度上能够被直接剪枝。假设历史上对变量 $x_{1}$ 进行分支时，经常出现某个子节点不可行或者 $LB\geq UB$ ，说明分支能够快速排除一部分搜索空间。

Node Selection

Node Selection 研究的是在分支定界算法中，存在多个尚未探索的节点时，应该优先探索哪一个节点才能提高整个 MILP 的求解效率。

假设节点 C、D、E、F 尚未探索，将其存放在一个待处理节点集合：

L = \{C,D,E,F\}

Node Selection 要解决的就是，接下来应该选择哪一个节点。不同的搜索顺序会影响多快能够找到一个较好的整数可行解、改善全局上界、能否尽早剪掉其他搜索节点、最终求解所需要的搜索节点数量和计算时间。可以将节点选择看成一个策略决策问题，可以定义：

\pi_{\theta}(s) = a

其中 $s$ 是当前 B&B 的搜索状态， $a$ 是准备探索的下一个节点， $\pi_{\theta}$ 是机器学习得到的节点选择策略。He et al. (2014)：Learning to Search in Branch and Bound Algorithms 采用模仿学习，学习节点选择策略（决定下一个探索哪一个节点）和节点剪枝策略（决定是否需要进一步展开当前节点），核心的思路是让模型学习专家的搜索行为，从而加快 B&B 的搜索过程。Yilmaz et al. (2020) 同样采用模仿学习，其主要关注当前节点的子节点选择，而不是直接对整个待探索节点集合进行全局排序。

Cutting Plane

割平面主要研究如何通过向 MILP 的线性规划松弛问题中添加新的有效约束，缩小搜索空间，并利用机器学习选择更有效的割平面，从而加速 MILP 的求解。

求解 MILP 时，通常会先去除掉整数约束，得到 LP Relaxation，例如：

\min x + y \newline s.t. x + y \geq 1.5 \newline x, y \in \{0,1\}

去除掉整数约束后，变成 $0\leq x,y \leq 1$ ，LP Relaxation 的一个最优解是 $x=0.75,y=0.75$ ，对应的目标值为 $z_{LP}=1.5$ ，但这个解不满足整数约束，而原本 MILP 的唯一可行的整数解为 $x = 1, y =1$ 。这说明了 LP 松弛的可行域实际上包含了很多 MILP 不允许的分数解，Cutting Plane 的思想就是添加新的线性约束来排除一部分这样的整数解，同时保留原来所有的整数可行解。例如在观察到 $x + y \geq 1.5$ 时，由于 $x,y$ 必须是整数，因此必然有 $x+y \geq 2$ ，可以将其作为新的割平面，这样最优值能够更快收敛。一个好的割平面可以显著收紧 LP 松弛，甚至在不进行分割的情况下就能够帮助找到最优解。割平面可以缩小搜索空间，但也并非越多越好，添加割平面可能加强 LP 松弛，但也会带来额外的开销，例如 LP 约束数量增加、求解时间变长以及数值稳定性问题，而且不同的割平面的实际效果不同。因此可以引入机器学习，来在割平面的有效性和计算开销之间做出决策，机器学习可以尝试建立一个评分函数：

s_{i}=f_{\theta}(S,c_{i})

其中 $S_{i}$ 是当前 MILP 搜索状态， $c_{i}$ 是候选割平面， $f_{\theta}$ 是用于预测割平面价值的机器学习模型。 Tang et al. (2020)将割平面的连续选择建模为马尔柯夫过程，然后利用强化学习训练选择策略：

\text{当前 LP 状态} \rightarrow \text{选择 Cut} \rightarrow \text{更新 LP} \rightarrow \text{获得反馈}

模型通过与求解过程进行交互，学习如何选择有利于整体优化效果的割平面，其还使用了进化策略来训练强化学习智能体。 Huang et al. (2021) 研究了 Cut Ranking，即对候选割平面进行排序。通过采用机器学习方法，根据割平面的相关特征预测评分，决定下一步优先选择使用哪些 Cut。

启发式算法

虽然可以利用 B&B 精确求解 MIP，但是由于其 NP-hard 的特性，求解可能需要大量时间和计算资源，对于大规模问题，B&B 可能变得难以处理，因此可以考虑采用启发式算法。

Large Neighborhood Search

大邻域搜索算法研究的是如何从一个已有的可行解出发，通过不断选择合适的搜索邻域，寻找更好的解，以及如何利用机器学习优化邻域选择，提高搜索效率。 LNS 是一种启发式优化算法，不要求证明找到的解一定是全局最优解，而是希望在有限计算时间内找到尽可能好的可行解。考虑一个 MILP 问题：

\min c^Tx

假设已经通过某种方法找到了一个整数可行解：

x^{(0)}=(1,0,1,1,0)

对应目标的函数值为：

f(x^{(0)})=100

现在希望找到一个更好的解，LNS 的方案是不重新求解整个问题，而是固定当前解中的一部分变量，只允许剩余变量发生变化，然后在这个局部搜索空间中寻找更优解，不断进行迭代寻找不劣于当前解的可行解。邻域指的是允许我们从 $x$ 出发搜索的一组候选解：

\mathcal N(x)

LNS 允许相当大的一部分变量共同变化，然后借助优化求解器搜索这个子空间，这里也会出现一个权衡：

邻域过小：容易快速求解，但可能难以找到明显更好的解。
邻域过大：更有机会找到好解，但是子问题可能非常难以求解。

LNS 需要做的决策主要有两个：Initial Solution 和 Neighborhood Selection。 LNS 通常需要一个初始的可行解：

x^{(0)} \in X_{feasible}

初始解的质量可能影响后续搜索的效率。 Neighborhood Selection 相对而言更加重要，其主要研究应该选择哪些变量进行重新优化，如果随意选择，可能浪费大量计算资源，而如果能够找到哪些对改善目标函数最重要的变量，就有希望快速得到优质解。Song et al. (2020 a)利用模仿学习和强化学习选择搜索领域；Sonnerat et al. (2021) 利用 Neural Diving 获取初始解，并学习领域选择；Liu et al. (2021)利用 ML 动态调整邻域的大小；Wu et al. (2021)将强化学习与 LNS 结合来改善搜索性能。

Feasibility Pump

Feasibility Pump 研究的是如何利用 LP 松弛解，通过反复进行取整和投影，快速找到满足 MILP 整数约束与线性约束的可行解，以及如何利用机器学习提高这一过程的效率。 FP 采取一种交替迭代的方式：

求解 LP Relaxation，获得满足线性约束的连续解。
Rounding（取整）：满足整数要求，但可能违反线性约束。
Projection（投影）：寻找接近当前整数点的 LP 可行解，通过最小化新解与当前整数点之间的距离 $x^{(t+1)} \in \arg \underset{x \in P}{\min} \underset{i \in I}{\sum}|x_i-\widetilde x_i^{(t)}|$ ,由于其使用的是 $L_{1}$ 距离，因此可以通过辅助变量将其转化为线性规划。
重新取整并检查可行性：成功则返回，否则继续迭代。

以上过程还可能会陷入循环，可以通过添加随机扰动来跳出。传统的 FP 在 Projection 阶段，总是趋向于选择距离当前整数点最近的 LP 可行解，但是实际上最近的点可能导致算法反复回到同一个整数点，使搜索陷入较差的循环。 Qi et al. (2021)利用强化学习改进 FP，让强化学习智能体决定下一步应该选择什么样的连续解，而不再完全依赖最近距离准则。此外还有两类神经网络设计：

MLP：利用 MILP 的相关状态特征进行预测。
CNN：将 MILP 的参数矩阵（例如 A，b）组织成类似图像的表示，进行特征提取。

Predit and Pick

Predit and Pick 解决的问题是利用机器学习更加有效地使用成熟的算法和求解器。例如对于不同的 MILP 实例，有的问题很容易通过启发式算法找到可行解，有的问题可能需要大量 B&B 搜索，有的问题可以通过预测较好的初始解来加速求解，有的问题包含大量冗余约束，导致求解器产生不必要的计算。因此可以让机器学习提前预测某些问题的性质，再据此来选择或调整求解的策略。 Ding et al. (2020)利用历史数据预测 MILP 中变量可能的解值，并结合启发式算法与精确分支方法进行求解，机器学习模型可以预测变量的取值，对于预测比较确定的部分，可以尝试是用启发式方法，对于预测不确定、难以处理的部分，则更多地依靠传统精确求解方法。此外，还可以让机器学习选择启发式算法。CPLEX 这类求解器内部包含多种预定义的启发式策略，但是不同 MILP 实例可能适合不同策略，因此可以让模型来自动选择。Grover et al. (2018)利用强化学习根据 MILP 实例特征，学习如何选择 CPLEX 中预定义的启发式方法。 Xavier et al. (2021)使用了 KNN 方法，主要预测目标包括以下内容：

冗余约束：尝试减少需要处理的约束。
较好的初始可行解：为求解器提供热启动。
最优解可能所在的仿射子空间：缩小重点搜索的空间。

参考文献

原文为 Zhang, J., Liu, C., Yan, J., Li, X., Zhen, H.-L., & Yuan, M. (2023). A survey for solving mixed integer programming via machine learning. Neurocomputing, 519, 205–217（doi:10.1016/j.neucom.2022.11.024，预印本 arXiv:2203.02878）。以下按正文首次出现的顺序列出被引工作：

Khalil, E. B., Le Bodic, P., Song, L., Nemhauser, G., & Dilkina, B. (2016). Learning to Branch in Mixed Integer Programming. Proceedings of the AAAI Conference on Artificial Intelligence, 30. doi:10.1609/aaai.v30i1.10080
Gasse, M., Chételat, D., Ferroni, N., Charlin, L., & Lodi, A. (2019). Exact Combinatorial Optimization with Graph Convolutional Neural Networks. NeurIPS 2019. arXiv:1906.01629 · NeurIPS 页面
Etheve, M., Alès, Z., Bissuel, C., Juan, O., & Kedad-Sidhoum, S. (2020). Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm. CPAIOR 2020, LNCS, 176–185. doi:10.1007/978-3-030-58942-4_12 · arXiv:2005.10026
Sun, H., Chen, W., Li, H., & Song, L. (2020). Improving Learning to Branch via Reinforcement Learning. Learning Meets Combinatorial Algorithms Workshop (NeurIPS 2020).
He, H., Daumé III, H., & Eisner, J. M. (2014). Learning to Search in Branch and Bound Algorithms. NeurIPS 2014. NeurIPS 页面
Yilmaz, K., & Yorke-Smith, N. (2020). A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP. arXiv:2007.03948
Tang, Y., Agrawal, S., & Faenza, Y. (2020). Reinforcement Learning for Integer Programming: Learning to Cut. ICML 2020, PMLR 119. PMLR 页面 · arXiv:1906.04859
Huang, Z., Wang, K., Liu, F., Zhen, H.-L., Zhang, W., Yuan, M., Hao, J., Yu, Y., & Wang, J. (2022). Learning to Select Cuts for Efficient Mixed-Integer Programming. Pattern Recognition, 123, 108353. doi:10.1016/j.patcog.2021.108353 · arXiv:2105.13645
Song, J., Lanka, R., Yue, Y., & Dilkina, B. (2020). A General Large Neighborhood Search Framework for Solving Integer Linear Programs. NeurIPS 2020. NeurIPS 页面 · arXiv:2004.00422
Sonnerat, N., Wang, P., Ktena, I., Bartunov, S., & Nair, V. (2021). Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs. arXiv:2107.10201
Liu, D., Fischetti, M., & Lodi, A. (2022). Learning to Search in Local Branching. AAAI-22, 36(4), 3796–3803. doi:10.1609/aaai.v36i4.20294 · arXiv:2112.02195
Wu, Y., Song, W., Cao, Z., & Zhang, J. (2021). Learning Large Neighborhood Search Policy for Integer Programming. NeurIPS 2021. NeurIPS 页面 · arXiv:2111.03466
Qi, M., Wang, M., & Shen, Z.-J. (2021). Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming. arXiv:2102.09663
Ding, J.-Y., Zhang, C., Shen, L., Li, S., Wang, B., Xu, Y., & Song, L. (2020). Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction. AAAI 2020, 34(2), 1452–1459. doi:10.1609/aaai.v34i02.5503 · arXiv:1906.09575
Grover, A., Markov, T., Attia, P., Jin, N., Perkins, N., Cheong, B., Chen, M., Yang, Z., Harris, S., Chueh, W., et al. (2018). Best Arm Identification in Multi-Armed Bandits with Delayed Feedback. AISTATS 2018, PMLR 84. PMLR 页面 · arXiv:1803.10937
Xavier, Á. S., Qiu, F., & Ahmed, S. (2021). Learning to Solve Large-Scale Security-Constrained Unit Commitment Problems. INFORMS Journal on Computing, 33(2), 739–756. doi:10.1287/ijoc.2020.0976