| 标题 | Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization:Cardinality, Minimum, Covering,and More |
|---|---|
| 作者 | Fanchen Bu，Hyeonsoo Jo，Soo Yong Lee，Sungsoo Ahn，Kijung Shin |
| 邮箱 | kijungs@kaist.ac.kr |
| 论文 | https://arxiv.org/pdf/2405.08424 |
| 代码 | https://github.com/ai4co/unsupervised-CO-ucom2 |
1. 摘要
组合优化（CO）本质上是离散的，这使得基于可微优化的机器学习方法不适用。Karalias和Loukas（2020）将概率方法应用于组合优化，融入可微优化框架。他们的工作激发了关于无监督学习在组合优化中应用的研究，主要包括两个组成部分：概率目标和去随机化。然而，这两个部分都面临不同的挑战。首先，在不同条件下（例如，基数约束和最小值）推导目标函数并不简单。其次，去随机化过程尚未深入研究，现有的去随机化方法要么是随机抽样，要么是简单的四舍五入。在本研究中，我们旨在解决无监督组合优化中常见的条件。首先，我们通过理论依据明确目标构建和去随机化的目标。接着，我们针对不同组合优化问题中常见的条件，推导出非平凡的目标函数和去随机化方法，以满足这些目标。最后，我们将这些推导应用于各种组合优化问题。通过对合成和真实世界的图问题的广泛实验，我们验证了推导的正确性，并展示了在优化质量和速度方面的经验优势。
3. 介绍
3.1 UL4CO
UL4CO的pipeline是基于概率模型的方法Erdos Goes Neural，其由三个部分组成，目标构建、可微分优化和去随机化。下面会依次介绍：
（1）概率目标构建：概括来说就是在决策分布上评估离散的目标，具体来说，给一个组合优化问题，我们首先构建一个惩罚目标。那么一个接收概率输入的概率目标函数：就可以被构建为：
我们将视为概率向量，是单独的伯努利向量，因此有：
（2）可微优化：即必须要确保是可微的，假设现在我们已经构建了这样一个，然后给定一个图，就可以使用可微优化如梯度下降来获得较小的的优化概率。
（3）去随机方法：最后，利用去随机化方法得到确定性的完全决策。对于每个测试实例，去随机化过程将通过概率优化得到的每个转化为一个离散的完整决策。
（4）局部去随机化：先前的工作通过迭代舍入的方法进一步证明了确定性的质量保证，即不依赖随机抽样的质量保证。迭代舍入德源里涉及两个概念①概率p的局部去随机化和②概率目标在每个分量上都是凹的。 ①对于局部去随机化，首先给定且，则是的一个分量去随机化后的结果，将其作为，例如：
注：这表示新的向量与原始的向量基本相同，只是在i的位置被替换为，因此这是局部去随机化的一种方法。 ②对于函数的逐元素凹性，一个概率目标是凹的，则要满足下面的条件：(凹性和非凸是不一样的)
3.2 先前工作UL4CO的不足
在UL4CO中有两个组成部分：(1)概率目标的构建和(2)非随机化以获得最终离散解。然而，先前关于UL4CO的工作有许多限制。首先，尽管已经提出了概率目标的一些理想属性（例如，理想目标应该是可微的，并且与原始离散目标很好地对齐），但如何推导满足这些属性的目标仍然不清楚。与此同时，对非随机化过程的探索不足，缺乏许多实用技术或理论讨论。现有的非随机化方法要么是随机抽样，要么是朴素舍入，随机抽样，就其本质而言可能需要进行大量的抽样才能得到好的结果，对于朴素舍入，性能可能高度依赖于舍入的顺序。这些都是悬而未决的问题，因此，在本文工作中，作者将重点放在UL4CO框架内尚未系统处理的目标和约束上，这些目标和约束通常涉及各种CO问题，例如基数约束、最小值、覆盖、团或独立集等。
4. 将概率目标具体化
4.1 概率目标
好的概率目标函数应该有怎么样的特性：(1)接收连续的输入，而不是离散的；(2)是惩罚目标期望的上界；(3)是可微的；(4)是逐元素凹的；**(5)和有相同的最小值；（此特性在之前的工作中未被显示地提出）**因此，目标1：构建一个概率目标函数，满足上述(1)~(5)的特性。
接下来，作者提出了构造满足上述五个特性的概率目标函数的方法，首先任何离散函数的期望都满足特性(1)(3)(4)，即对于所有，都有是可微和逐元素凹的。那么为了满足特性(2)和(5)，只需要找到一个惩罚目标的紧上界(TUB)。定义1：（紧上界）给定，我们说是的一个紧上界，当且仅当对于所有都有，且，，其中。最后，我们提出以下具体目标来构造紧上界的期望。目标1：（构建一个TUB的上界）给定带有约束的目标函数，设，则目标是找到，其中是的TUB，而是的TUB，则构建的概率目标函数为：
4.2 快速有效的去随机化：用贪婪和增量的方式实现
目标是提出一种速度快且有效地生成高质量解的去随机化方案，为此，我们将贪心算法推广到贪心非随机化，并提出了一种提高速度的增量方案。对于贪心去随机化，从开始，重复以下步骤：①我们贪婪地寻找最佳的局部非随机化，例如②执行：。
贪婪非随机化是对现有去随机化方法的改进，随机抽样保证了离散，迭代舍入保证了离散和优于最初的，但是问题在于时间复杂性方面，普通的方法仍需要在每一步对概率目标函数进行2n次评估，因此，作者建议以增量的方式进行去随机化，以提高速度，作者的直觉是：增量差通常比整个函数更简单，并且增量差的计算很容易并行化。因此得到了以下目标：目标2：（进行增量贪婪去随机化）增量差分对于所有对有。
5 推导公式以满足目标
对于不同CO问题中通常涉及的各种条件（基数约束、最小值、覆盖、团或独立集、非二进制决策），作者将推导出(1)基于TUB的概率目标以满足目标1和(2)的增量差分（IDs）以满足目标2。使用下面的模板来处理每种情况。注意，为每个条件派生TUB和ID需要不同的、重要的思想。
5.1 基数约束
问题定义：考虑对的约束为，一些典型的例子是或，例如只能选择固定数量k或小于k件物品。给定，则满足泊松分布，因此概率质量函数(PMF)为：
（S1-1）我们得到是到可行基数集的最小距离，即是的紧上界。（S1-2）那么我们推导出，主要的难点在于泊松二项分布的PMF的计算，因此采用了基于离散傅里叶变换的方法。
（S2）利用泊松二项分布导出了的IDs。即对于所有的，设和，则有：
基于此，可以推导出：
其中，对于小于等于0.5则使用方程(1)，对于大于0.5则使用方程2。
5.2 最小化或最大化一个子集
问题定义：考虑这样的约束，有一个接收点对的得分函数（例如计算距离），那么目标是对于一些计算，例如计算一个集合内点的最短距离。
（S1-1）我们发现就是源目标函数，其就是的一个紧约束(TUB)。（S1-2）我们通过将目标分解为子项，得到，因此对于所有有：
（S2）通过分析哪些子项在局部去随机化后出现了变化来推导出的IDs，即对于所有和，设为的系数，则推导出的IDs为：
5.3 覆盖
问题定义：考虑某些节点需要被覆盖（即至少i的一个邻居被选择），将约束公式化，即。
（S1-1）我们发现是原约束的指示函数，其就是的一个紧约束。（S1-2）我们通过将目标分解为子项推导出：
即对于所有和有：
（S2）通过分析哪些子项在局部去随机化后出现了变化来推导出了IDs，即对于所有和得到，若则若，则：
5.4 团或最大独立集
问题定义：考虑结点应该形成一个团，则公式化约束为。
（S1-1）我们得到为所选结点对未被约束的个数，其就是的一个紧上界。（S1-2）通过将目标分解为子项推导出：
（S2）同样推导出IDs，即对所有和有：
在论文中还介绍了一些在CO中常用的条件如非二进制决策、边存在的不确定性等等，在这里不再赘述。作者的衍生中常用的技术包括**(1)将目标分解为子项，(2)分析哪些子项在局部去随机化一步后发生了变化。**这种“局部可分解性”允许作者使用期望的线性。
6 应用到实际的CO问题上
将应用于不同的CO问题（设施位置，最大覆盖和着色问题），对于每个具体问题，我们将(1)检查问题涉及哪些条件，(2)结合第5部分的分析构建概率目标和去随机化过程。
6.1 设施位置
有一个带权重的图，任务的目标是选择固定数量的结点（设施），使得所选择的子图中的权重最小，因此此问题设计两个条件①基数约束和②最小化子集。则对于所有和，得到的概率目标函数和IDs分别为：
实验结果如下：
6.2 最大覆盖
最大覆盖问题是现实世界应用的经典CO问题，包括公共交通管理、网络管理和调度。给定m个项目，每个边都有权重，有一个n个集合的簇，目标是从给定的集合中选择k个，被覆盖的总权重最大。因此此问题涉及两个条件①基数约束和②覆盖。因此构造一个二部图，其中当且仅当则，则对于所有和，得到的概率目标函数和增量差分分别为：
实验结果如下：
6.3 鲁棒着色
鲁棒着色问题概括了着色问题，其动机是现实世界的调度问题，其中一些冲突可能是不确定的。给一个不确定的图，P表示每条边发生冲突的概率，和种颜色，设为必须要避免的硬冲突，即发生冲突的概率为1，也就是肯定会发生冲突，及为尽可能避免的软冲突，即发生冲突的概率为，目标是为每个顶点都找到一个颜色，且当图发生变化时，这些节点应满足两个约束：①不违背硬约束，即的边两个端点的颜色不能相同；②不违反软约束的概率要最大，即要最大，也就是说可以发生冲突的边，不发生冲突的概率要最大。因此此问题涉及三个条件①独立集②不确定的图③非二进制决策，即决策变量的值为三个或三个以上。 对于约束1，有，其是的一个紧上界，对于约束2，就等同于最大化其本身可以作为自己的紧上界，则对于所有两个概率目标函数为：
则两个增量差分分别为：
则总增量差分IDs为：。
实验结果如下：
如表3所示，在运行时间最少的情况下，UCOM2在大多数情况下始终实现了(1)优于两个贪婪基线和DC的优化质量，(2)优于Gurobi的优化质量。即使我们只为UCOM2使用cpu，这种优势仍然存在，当使用gpu时，UCOM2甚至更快。
7. 总结及未来工作
我认为尽管深度学习取得了巨大的成功，基于概率的方法在解决某些类型的组合优化问题时，仍然具有不可替代的优势，首先基于概率的方法有数学理论支持，具有可解释性，其次面对离散的组合优化问题，深度学习方法往往要进行某些近似，且缺乏明确的损失函数，而基于概率的方法可以直接对问题进行设计，最后，现实世界的问题有很多不确定性和噪声，给予概率的方法可以很好地处理这种不确定性。而在本文工作中，作者对UL4CO中的不足进行了探究，通过理论论证（定理1和定理2）具体化了概率目标构建和去随机化的目标，推导了各种条件（例如，基数约束和最小值）的非平凡目标和去随机化，以满足目标，并将推导应用于涉及此类条件的不同问题，通过广泛的实验证明了此方法的优势。虽然本文并没有涵盖组合优化中所有的条件，但是这种思想适应于其他的条件和问题。
