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 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.
Abstract (translated)
局部搜索是一种有效的方法,用于解决大规模的组合优化问题,并在近年来通过几个微妙的机制取得了显著进展。在本文中,我们发现了两种方法,以改进局部搜索算法,解决伪布尔优化问题(PBO)。第一种方法是将一些机制,如单元传播,仅仅用于解决MaxSAT之前,这些机制可以扩展到解决PBO的问题。第二种方法是,现有的局部搜索算法利用称为评分的变量启发式,主要用于指导搜索。我们试图更深入地了解条件,因为它是构建变量和给定公式之间的桥梁的中介。因此,我们首先将单元传播组合算法扩展到PBO问题,为PBO问题提供了进一步扩展的定义,并将其应用于现有的LS-PBO解器,以构建初始解集。然后,我们引入了一种新的条件启发式,称为护理,为当前迭代中的条件设置更高的优先级。对三个实际应用领域基准的的实验包括最小宽度信任带、无线传感器网络优化和座位安排问题,表明,我们的算法 DeciLS-PBO相对于最先进的算法具有令人期望的性能。
URL
https://arxiv.org/abs/2301.12251
