An effective local search method for pseudo-boolean optimization

Local search method is a rising star for solving combinatorial optimization problems in recent years, and many state-of-the-art local search-based incomplete Maximum Satisfiability (MaxSAT) solvers show promising performance even competitive to many complete solvers in recent MaxSAT Evaluations. However, to the best of our knowledge, studies on solving pseudo-Boolean optimization (PBO) by local search method are very limited, the solver LS-PBO proposed by Prof. Cai is the first local search-based PBO solver in recent years. Researchers found some mechanisms can be used to improve the performance of LS-PBO.

To solve the problem, a research team led by Dantong OUYANG published their new research on 15 April 2024 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.

The team proposed a new local search method for solving pseudo-Boolean optimization problem. Based on the work of LS-PBO, they presented two new components including a new initial solution generation method and a new heuristic defined on clauses to improve the solver’s performance. The new method is tested in many real-world application instances as well as 1600 instances from the most recent PB competition. Compared with the existing complete and incomplete PBO solvers, the proposed method can obtain the greatest number of best solutions, which indicates a promising performance of the new solver.

In the research, they apply the technique called unit propagation to generate a better initial solution and then the algorithm goes into a loop to improve it. In order to apply this technique to PBO problem, they extend the notions of ‘unit clause’ to PBO. Unit propagation has been widely used in solving satisfiability problem before, and it works by collecting all unit clauses, and then assigning their literals to be true to satisfy all the unit clauses. It provides an intuitive way to improve the quality of the initial solution. Besides, local search algorithms have a common phenomenon that they are easy to trap into a local optimum. The team also proposes a new scheme to help the algorithm find a feasible solution faster when it falls into a local optimum. They find the existing local search algorithms utilize the heuristic defined on variables to mainly guide the search. However, clauses, as intermediaries who build a bridge between variables and the given formula, are also important information for the algorithm. Thus, they introduce a new heuristic defined on clauses to guide the search focus on clauses that are always falsified, so the algorithm can obtain a feasible solution faster.

Firstly, they evaluate DeciLS-PBO on PBO instances from three real-world application problems, including minimum width confidence band, wireless sensor network optimization, and seating arrangement problems. They also evaluate the new solver on 1600 benchmarks from the most recent Pseudo-Boolean Competition. Experimental results show that DeciLS-PBO outperforms its competitors on most benchmark instances and its performance far exceeds the complete solver on large-scale instances, which indicates the superiority of the new solver.

Future work can focus on finding more subtle mechanisms to improve local search methods, and designing a more effective method for solving large-scale pseudo-Boolean optimization problem.

DOI: 10.1007/s11704-023-3018-8