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.

本文通过两种方法提高局部搜索算法的效率解决了伪布尔优化问题 (PBO)。首先使用一些机制 (如单位传播) 将其广义化为 PBO 问题，然后利用措辞这个桥梁来增强对其的理解。实验表明我们的算法比现有算法性能更好。

DeciLS-PBO: 一种有效的伪布尔优化局部搜索方法

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

We present a new approach to enhancing Answer Set Programming (ASP) with
Constraint Processing techniques which allows for solving interesting
Constraint Satisfaction Problems in ASP. We show how constraints on finite
domains can be decomposed into logic programs such that unit-propagation
achieves arc, bound or range consistency. Experiments with our encodings
demonstrate their computational impact.

本研究提出了一种新的方法，将约束处理技术与 Answer Set Programming（ASP）相结合，可以解决 ASP 中的有趣约束满足问题，并显示如何将有限域上的约束分解成逻辑程序，以便使用单元传播实现弧、束或范围一致性，并且对编码进行的实验表明它们的计算影响。

基于翻译的约束答案集求解方法

A Translational Approach to Constraint Answer Set Solving

We show that tools from circuit complexity can be used to study
decompositions of global constraints. In particular, we study decompositions of
global constraints into conjunctive normal form with the property that unit
propagation on the decomposition enforces the same level of consistency as a
specialized propagation algorithm. We prove that a constraint propagator has a
a polynomial size decomposition if and only if it can be computed by a
polynomial size monotone Boolean circuit. Lower bounds on the size of monotone
Boolean circuits thus translate to lower bounds on the size of decompositions
of global constraints. For instance, we prove that there is no polynomial sized
decomposition of the domain consistency propagator for the ALLDIFFERENT
constraint.

使用电路复杂度工具研究全局约束的分解，证明约束传播器存在一个多项式大小分解，当且仅当可以通过一个多项式大小单调布尔电路计算，并证明领域一致性传播者不存在多项式大小分解。