7777.mp4
7777.mp3
Deep Cooperation of Local Search and Unit Propagation Techniques
Full Text
Share
Xiamin Chen from Shanghai University of Finance and Economics, tells us that Local search (LS) is an efficient method for solving combinatorial optimization problems such as MaxSAT and Pseudo Boolean Problems (PBO). But due to the lack of reasoning power and global information, LS methods get stuck at local optima easily. In contrast, systematic search utilize unit propagation and clause learning techniques with strong reasoning power to avoid falling into local optima. However, the complete search is generally time-consuming. This work proposes a deep cooperation framework of local search and unit propagation to address their inherent disadvantages. First, we design a mechanism to observe the stuck situation of the LS, and then a well designed unit propagation procedure is called to help get out of the local optima. Experiments based on MaxSAT Evaluations, PBO competition , the Mixed Integer Programming Library and real-life cases validate that our method can bring huge improvements in state-of-the-art MaxSAT and PBO LS solvers