ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization#

PBO Problem#

我们首先给定什么是 PBO 问题：

\begin{aligned}
\min_{\{x_1, \dots, x_n\}} \, &\sum^n_{i=1}c_i \cdot l_i, \quad c_i \in \mathbb{Z} \\
s.t. \quad &\bigwedge^m_{j=1}\sum^n_{i=1}a_{ji}\cdot l_i \geq b_j, \quad a_{ji}, b_{j} \in \mathbb{N^+_0}
\end{aligned}

Related Work#

解决 PBO 的算法主要分为以下几类：

1. PB 求解器，代表为 Sat4J，RoundingSAT，HYBRID
2. 分支限界法（BnB），例如最大碰集，线性规划（松弛约束）
3. 编码为 SAT 求解，例如 MINISAT+， OpenWBO
4. 混合整数规划期，例如 SCIP，Gurobi
5. 不完备的局部搜索算法

对于局部搜索算法，最有代表性的莫过于 LS-PBO SAT'21 算法； 随后，在此基础上，DeciLS-PBO FCS'23 提出了通过使用基于单位传播的方法产生更好的初始解的方式，改进了 LS-PBO ； 最近，NuPBO CP'23 提出了一种新的打分函数与加权策略，进一步提高了 LS-PBO，成为 SOTA 的求解器

对此，本文首先提出一种 LS-PBO 的改进 DLS-PBO，并在此基础上提出它的并行版本 ParLS-PBO

Review of LS-PBO#

LS-PBO 作为 PBO 局部搜索求解器中的代表（也是其他局部搜索求解器的核心部件），其核心的思想为以下两点：

1. 约束加权方案
2. 打分函数

例如一个 PBO 问题，LS-PBO 期望找到这样一个解（假定目标为最小化）：，其中 表示目标函数在本次搜索时找到的最优值

LS-PBO 使用加权技术来增加未满足的约束的权重，使搜索过程偏向于满足它们，具体而言，其动态调整这些权重，这里我们用 来表示。

对于打分函数，在 LS-PBO 中，对于翻转一个变量 ，我们将收益表示为以下形式：

score(x) = hscore(x) + oscore(x)

其中， 表示翻转 后未满足的硬约束满足了多少（或者减少了多少惩罚值）， 表示翻转 后，目标函数（软约束）满足了多少（或者减少了多少惩罚值）

我们将硬约束的惩罚定义为 ，目标约束的惩罚值定义为

DLS-PBO#

但我们发现，LS-PBO 缺少对软硬约束比例的动态调整，换而言之，在长时间找不到可行解时，我们应该提高硬约束的在打分中的占比，使得我们能够快速找到一个可行解；相反，如果我们能够快速找到可行解，那么我们应该提高软约束在打分中的比例，使得我们能够寻找到更好的可行解

于是，我们提出一种动态评分机制，定义如下：

score^*(x) = hscore(x) + p \cdot oscore(x)

其中， 是一个动态值，初始化为 ，我们做如下更新：

1. 如果我们在最近的 次迭代中，都没有找到可行解，我们将 调整为 ，其中
2. 否则，我们将其调整为

\begin{aligned}
\min_{\{x_1, x_2, x_3\}} &10 \cdot x_1 + 20 \cdot x_2 + 30 \cdot x_3 \\
s.t. \quad &2 \cdot x_1 + 3 \cdot x_2 + 4 \cdot x_3 \geq 5
\end{aligned}

并行化 ParLS-PBO#

框架#

ParLS-PBO¹ 的总体框架如下所示

具体而言，并行框架由一个 master² 线程和多个 worker 线程组成，其中 master 线程负责读取实例并通过 literal assume 为 worker 初始化不同的赋值（部分赋值），当时间耗尽后，master 线程会给出搜索到的最优解。

每个 worker 线程收到一个文字 或者 后，会直接做单元传播，简化约束与目标函数，然后，worker 开始局部搜索，也就是上文提到的 #DLS-PBO

Solution Pool#

为了使得不同的 worker 线程能够获取各自的信息（以求得更好的解），这里引入了解池的概念

当一个 worker 线程的搜索过程在翻转一定数量的变量后卡在局部最优时，就会尝试使用解池中的高质量的可行解，然后重启，继续进行搜索。

那么这里，如何评价一个解是否够好（是否需要被加入到解池中）呢？我们考虑一个混合质量排名函数：

r_{mix}(S) = rank_{obj}(S)\cdot p^* + rank_{div}(S) \cdot(1-p^*)

其中， 分别表示 在解池中的目标函数排名与多元化值排名，，用于控制哪个排名的占比更大

最优解的目标函数值时最小的，于是 ，多元化值最大的排名最高，定义为 ，我们定义多元化值的计算方式为：

当 worker 线程找到一个新的可行解时，如果解池未满，则直接加入，否则，计算这个解的 ，并与解池最大的 比较，如果 ，那么我们会将新的解加入，将最差的解剔除

如何使用 Solution Pool#

我们在 前文 中提到了，解池能够指导搜索，具体而言，解池通过以下两个策略来指导搜索过程

Solution Sharing#

当 worker 线程在一段时间内未能找到较好的可行解，即可能陷入局部最优时，从解池中选择目标函数值较小的可行解并替换当前可行解

在实际应用中，每个工作线程保存当前最优可行解(记为 )以及相应的目标值 。当搜索过程在 步之后未能找到较优解时，从解池中挑选一个解后重启

为了防止不同线程之间搜索空间的过度重叠，我们采用基于概率的方法来选择池中的解决方案，而不是直接选择池中的最佳解决方案。具体地，假设 表示目标值不大于 (集合不会为空,因为它至少包含 )的解池中可行解的集合， 表示 目标值与 的差值。则选择 的概率为

Polarity Density Weight#

我们提出了变量 的极性密度权重的概念，记为 ，它反映了 在高质量解中出现的某种极性的偏好

最开始时，我们将其初始化为 ，随着高质量解 被加入到解池后，我们按照以下规则进行更新：

w_{pd}(x) = \begin{cases}
&\max (w_{pd}(x) - \beta, 1-\epsilon), \, if \, x = 0 \in S \\
&\min (w_{pd}(x) + \beta, 1+\epsilon), \, if \, x = 1 \in S
\end{cases}

极性密度权重用于增强搜索过程中挑选一个变量进行翻转的打分函数。由此得到的增强型得分函数，记为，定义如下：

score^{**}(x) = \begin{cases}
&score^*(x) \times w_{pd}(x), \, if \, x=0 \in S_{cur}\\
&score^*(x) / w_{pd}(x), \, otherwise
\end{cases}

其中 表示当前由局部搜索获得的当前赋值

实验#

使用 Benchmark 为：

1. 真实世界的例子，Minimum-Width Confidence Band Problem， Seating Arrangements Problem， Wireless Sensor Network Optimization Problem
2. MIPLIB 中的例子
3. PB16 中的例子

对比了以下算法：

1. LS-PBO³
2. DeciLS-PBO⁴
3. NuPBO⁵
4. HYBRID⁶
5. PBO-IHS⁷
6. Gurobi⁸
7. SCIP⁹
8. FiberSCIP¹⁰

其中，HYBRID 与 PBO-IHS 都是基于 RoundingSAT 更改的 PBO 版本

选择的参数如下表：

#win 表示求解器在被测试的求解器输出的所有解中找到最优解的实例数（获胜实例的数量）

DLS-PBO 的实验的结果如下表：

ParLS-PBO 的表现如下表