机器学习与组合优化

ML4CO

[1]组合优化和分支定界的背景：pdf

[2]GNN做branching的经典文章：pdf

[3,4]GNN在线性优化/组合优化问题上表达能力和逼近能力的理论基础：pdf pdf

[5]通用近似定理：pdf

[1]要点梳理

1 Introduction

分支定界法递归地将解空间以搜索树的形式划分，然后计算松弛问题的解，再对不能达到比现有解更优的子树进行剪枝。这个反复迭代的过程需要进行顺序决策（sequential decision making），如节点选择（node selection），即选择下一个做子问题拆解的结点；以及变量选择（variable selection），选择对于哪个变量进行划分子树。这种决策过程通常服从一系列由专家设计的硬编码的（hard-coded）（1）启发式规则。这些规则的目的是最小化在一组代表性MILP实例上的平均解决时间。但是在很多语境下经常需要反复求解一系列相似度的组合优化问题，这些问题可能与通常用来评估分支定界算法的实例集合有显著差异（2）。因此，使用统计学习方法是具有吸引力的；然而这面临着一些挑战。

编码MILP B&B决策过程的状态并不容易，尤其是因为搜索树和整数线性规划都可能具有可变的结构和大小；
如何构建一个模型架构，以便产生可以至少泛化到类似实例，理想情况下还能泛化到训练期间未见过的更大实例的规则，这一点也不清楚。

文章提出用图卷积网络（GCNN）来解决上面的问题。文章专注于变量选择问题，也就是分支问题（branching problem），这一问题是B&B范式的核心，但从理论上来说仍未被充分理解。文章采用模仿学习策略来快速近似强分支（strong branching），这是一种高质量但成本高昂的分支规则。

虽然上述想法不算新颖，文章基于此有两点主要贡献：

将branching策略编码到GCNN中，这使得能够利用MILP问题的自然二分图表示，从而减少手动特征工程的工作量；
使用行为克隆和交叉熵损失来近似强分支决策，这比预测强分支得分或排名更为简单。

文章在四类NP难题上评估了上述方法，包括集合覆盖、组合拍卖、有容量的设施定位和最大独立集问题。结果表明，文章选择的模型、状态编码和训练程序导致的策略在传统分支规则上有显著的改进，并且能够很好地泛化到比训练中使用的更大的实例。

1.理解为这些规则是预先设定并固定在算法中的，而不是在运行时动态生成或学习的；

2.暂时理解为泛化性能不佳，只能在一些相似的问题上，strong branching才有效。

3 Background

3.2 分支规则

到目前为止，一致性的分支策略结果表明，在所有 B&B 树中选择最小树是有力的分支。它通过在每个可能的分支点运行强分支来实现，这个分支计算每个候选变量在解决问题的预期贡献，并为每个候选变量选择最好的下界。然而，强分支不幸地需要为每个候选变量解决两个线性规划（LP），而在每个节点上运行强分支在实践中是不现实的，现代 B&B 求解器转而依赖于混合分支，它通过在仅在求解过程的开始计算强分支得分然后逐渐借还到更简单的启发式方法如：冲突得分（conflict score）或伪成本（pseudo-cost）或两者的人工组合。

3.3 马尔可夫决策过程公式化

B&B 过程中做出的连续决策可以被同化为马尔可夫决策过程。考虑一个求解器作为环境，分支器（brancher）作为代理。在第个决策中，求解器处于一个状态，该状态包括了 B&B 树的所有过去分支决策，到目前为止找到的最佳整数解，每个节点的 LP 解，当前关注的叶节点以及其他任何求解器统计信息（例如，调用了多少次每个原始启发式算法）。然后分支器从当前关注的节点的所有分数变量中选择一个变量，根据一个策略。然后求解器扩展 B&B 树，解决两个孩子 LP 松弛，运行任何内部启发式，如果合适就剪枝树，并最终选择下一个要分割的叶节点。我们随后处于一个新状态，并且分支器再次被调用来做出下一个分支决策。这个过程如下图所示。

作为马尔可夫决策过程，B&B 是 episodic 的，其中每个 episode 相当于解决一个 MILP 实例。初始状态对应于在一组兴趣中采样的实例，而最终状态标志着优化过程的结束。轨迹的概率取决于分支策略和求解器的其余组件，因此可以表示为：

注：原文这里的公式可以简化。其推导见这里

我的疑问

文章只针对进行学习，但是具体是怎么得到的我还不清楚。换言之选取了后，具体怎么划分子问题？这应该超出了“branching”的范畴。

4 Methodology

由于B&B变量选择问题可以被表述为马尔可夫决策过程，因此训练策略的自然方式是强化学习。然而，这种方法遇到了许多问题。值得注意的是，由于episode length与性能成正比，而随机初始化的策略表现不佳，标准的强化学习算法在训练初期通常非常慢，以至于总训练时间过长。此外，一旦选择了与实例对应的初始状态，剩余的过程就是实例特定的，所以马尔可夫决策过程往往非常庞大。在这项工作中，我们选择直接从一个专家分枝规则中学习，这种方法通常被称为模仿学习。

4.1 模仿学习

先跑expert程序得到专家的决策组合，利用交叉熵损失：

4.2 状态编码

的编码。考虑携带特征的二部图含义列举如下：

Tensor	Feature	Description
	obj_cos_sim	Cosine similarity with objective.
	bias	Bias value, normalized with constraint coefficients.
	is_tight	Tightness indicator in LP solution.
	dualsol_val	Dual solution value, normalized.
	age	LP age, normalized with total number of LPs.
	coef	Constraint coefficient, normalized per constraint.
	type	Type (binary, integer, impl. integer, continuous) as a one-hot encoding.
	coef	Objective coefficient, normalized.
	has_lb	Lower bound indicator.
	has_ub	Upper bound indicator.
	sol_is_at_lb	Solution value equals lower bound.
	sol_is_at_ub	Solution value equals upper bound.
	sol_frac	Solution value fractionality.
	basis_status	Simplex basis status (lower, basic, upper, zero) as a one-hot encoding.
	reduced_cost	Reduced cost, normalized.
	age	LP age, normalized.
	sol_val	Solution value.
	inc_val	Value in incumbent.
	avg_inc_val	Average value in incumbents.

4.3 branching 规则的参数化

网络结构如下：