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 状态编码

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

4.3 branching 规则的参数化

网络结构如下：

Functional Analysis

占坑，泛函分析复习笔记，内容大概有：

• 到2.2章节除了1.5章所有作业题解答以及部分未布置的题；
  • faMidNotes.pdf 部分笔记，剩余习题有的不在范围内，选择性重做一遍。
• 部分定理手动证明；
• 往届期中真题自己的解答；（不正式写了）

Ciarlet 相关有趣的内容整理（期中前）

易混淆的点：

• 是指的所有线性包（即 有限 线性组合）的并；
• 基要满足两点：
  • 向量族的元线性无关，即对于任意有限子集各元素线性无关；
  • 对于任何 ，都存在有限子族 ，被子族里面的向量线性表示。
  • 注意：任意向量空间均存在基（引理），且基的基数唯一确定。

补充例子与结论

强调（1.3里面常用结论）

• 中任意有界集为列紧集；
• 列紧空间的任意（闭）子集都是（自）列紧集；
• 列紧空间必是完备空间；
• 完全有界的度量空间可分。

定理 任何有限维空间均是可分的。

要证明这个定理，首先有：有限维空间的范数相互等价，于是换一个范数证明可分。

设为的一组基，对于扩充的实数，定义映射：

则有为上的范数，且空间是可分的，取坐标为有理数的点即可。

定理 设为可分的空间，则存在的有限维子空间的可数有限族满足：

证明 由稠密性，设，满足

首先可以假设对任何。此时递推地定义向量族为：

那么，满足所有条件。

定理 任意向量空间均可赋范。

证明 取的基，对任意给定向量，唯一地存在有限子族，被子族里面的向量线性表示。 此即 ，那么下面映射就是上的一个范数:

定理 赋范空间，可有内积给出满足平行四边形法则。并且满足平行四边形法则时，是内积。

定理 是可分的。时不可分。

证明 不妨证的情况，时构造稠密子集如下： 时，考虑为中所有以组成的数列集合，则，且是不可列的。设是中任意稠密子集，任给，存在，故映射为单射，不可列，从而不可分。

定理 为中的开子集，上紧支集连续函数在中稠密。是可分空间，时不可分。

在中稠密，时不稠密。

强调（有限维的情况）

• 任意两个范数等价；

• 任何有限维赋范空间可分；

• 对于有限维赋范空间中的子集，紧等价于有界闭；

• 空间的有限维子空间在中闭；

• 空间是有限维的等价于的单位球面列紧。

证明第三条：对于，由于紧蕴含有界闭只需反过来证明自列紧。取的基，有界推得各个系数有界，故找到了收敛的子列，这证明了自列紧。

定理 为任意向量空间，则在上存在不等价的范数。

证明 取的基​，那么下面映射就是上的范数:

这时取一个中的可数子族，不妨设为，令，得到。

定理 为赋范空间且 是有限维的，则由 到 的任何线性算子均是连续的。

证明 选取基展开，证明。

定理（投影映射相关）

是内积空间中的非空闭凸子集。为投影映射，代表的是关于的最佳逼近元。

• 为连续映射，常数为1。
• 为线性的充要条件是是的子空间，此时的算子范数为1。

定理（正交补相关）

是内积空间中的非空子集。

• 是的闭子空间；
• ；
• 如果是闭的，。

定理（空间中的表示定理）

为上的空间，对任意给定的，存在唯一的向量，使得而且。

例子（空间中不是闭的子空间）

在希尔伯特空间中构造一个不是闭集的子空间的经典例子是考虑无限维空间中的有限维子空间。

以序列空间 为例，这是所有平方可和的复数序列构成的空间。一个元素 满足 。在这个空间中，我们可以考虑子空间 由所有最终变为零的序列构成，也就是说，对于 中的每个序列 ，存在一个整数 使得所有 的 。

尽管 是 的一个线性子空间，它不是闭的。这是因为可以构造一个序列的序列（也就是一个序列的极限），这个极限在 中，但不在 中。例如，考虑序列 其中 是一个序列，它的前 个元素是 ，之后的元素都是零。每个 都在 中，但它们的极限是序列 ，这个极限在 中但不在 中，因为没有一个点使得序列之后的所有元素都是零。

因此， 是 中的一个不闭子空间的例子。

Ciarlet 相关有趣的内容整理（期中后）

未完待续...

实分析补充练习与补充知识点

6.30

设定义在上的函数满足$|f(x)-f(y)|e^{|x|+|y|}|x-y| Em(E)=0m(f(E))=0$。

不妨设为有界集，因为对每个，可令，这样就有，再由即得结论。

对于有界零测集，设。任给，存在开集，且。对使用开集结构定理，任意构成区间满足，故，这便证明了。

设是上的连续函数，是上的实值可测函数，则是上的可测函数。

上可测函数列满足，且依测度收敛到0，证明。

是上的正值可积函数，是一列可测子集，且有，证明。

设存在一列，那么足够大时。选取的子列使得在第项上的积分值小于。简便起见，这个子列仍记为。定义，作为Fatou-Lebesgue定理的直接推论，其测度。我们有： 这推出在上几乎处处为零，与题设矛盾。

7.1

补充上面的定理证明：

补充1 Fatou-Lebesgue定理

对于给定的度量空间 ，假设是一系列定义在其上的实值可测函数。如果存在一个勒贝格可积函数在上以绝对值控制该序列，即对于所有自然数，都满足，那么： 证明：所有的 以及 的下限和上限序列在绝对值上被 控制，因此它们是可测的，并且是可积的。第一个不等式是通过将非负函数 应用于Fatou引理，并利用Lebesgue积分的线性性得到的。最后一个不等式是反向Fatou引理。这里的Fatou引理比我们学的要强一些（周民强4.2例题4），我们学的是非负函数列+几乎处处收敛，这里的条件是，其形式是：