DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization#

Abstract

Local search is an effective method for solving large-scale combinatorial optimization problems, and it has made remarkable progress in recent years through several subtle mechanisms. In this paper, we found two ways to improve the local search algorithms in solving Pseudo-Boolean Optimization (PBO): Firstly, some of those mechanisms such as unit propagation are merely used in solving MaxSAT before, which can be generalized to solve PBO as well; Secondly, the existing local search algorithms utilize the heuristic on variables, so-called score, to mainly guide the search. We attempt to gain more insights into the clause, as it plays the role of a middleman who builds a bridge between variables and the given formula. Hence, we first extended the combination of unit propagation-based decimation algorithm to PBO problem, giving a further generalized definition of unit clause for PBO problem, and apply it to the existing solver LS-PBO for constructing an initial assignment; then, we introduced a new heuristic on clauses, dubbed care, to set a higher priority for the clauses that are less satisfied in current iterations. Experiments on benchmarks from the most recent PB Competition, as well as three real-world application benchmarks including minimum-width confidence band, wireless sensor network optimization, and seating arrangement problems show that our algorithm DeciLS-PBO has a promising performance compared to the state-of-the-art algorithms.

核心思想#

初始化更好的赋值#

首先，我们通过 IGUP-Decimation 来初始化赋值，此算法如下图所示：

做法与 LS-ECNF 中的 GUP 十分类似，在这里，对于一条 PB 约束，我们定义 generalized unit clasue 如下：

如果文字的系数最大，且满足，我们将这个文字称为 1-of-all 的广义单元子句
如果恒成立，那么我们成这条约束为广义单元约束
广义单元约束中的每一个文字都是一个 all-of-all 广义单位子句

现在，给定一个广义单元约束，最高系数的文字一定是一个 1-of-all 广义单元子句

于是，我们的做法为，首先找到所有的 1-of-all 与 all-of-all 广义单元子句，将这些广义单位子句赋值为真，这样，我们就能简化 PB 约束

主框架如下图所示：

在获取到初始赋值后，我们进入迭代搜索，这里主要需要注意几点：

打分函数，这里的打分函数与 LS-PBO 中的一致
约束加权，策略与 LS-PBO 的一致
如何跳出局部最优

跳出局部最优#

这里使用了一种名为 Care-FC scheme 的启发式策略，首先，我们定义对于一个 PB 约束，其表示其未满足的次数

unsat_count[c] 就是上文提到的，最开始时会初始化为，每次调用 update_hardunsatcount 时进行更新，代码如下所示：

void Satlike::update_hardunsatcount(){
	int i,c;
	for (i = 0; i < hardunsat_stack_fill_pointer; ++i){
		c = hardunsat_stack[i];
		unsat_count[c]++;
	}
}

本质上的思想就是，当陷入局部最优时且当前解还不是一个可行解：

以的概率随机选一个不满足的硬约束，然后从里面选得分最高的变量翻转
否则，以的概率，选择那些 care 值较高的，因为这样的约束很可能很久都没有被选中

注意，这个函数在 flip 后会被调用一次，更新 care 值

实验#

实验效果其实不算很好，Benchmark 比 NuPBO 也少了两个，比一下共同的：

DeciLS-PBO 阅读笔记