Item


Deep Cooperation of Local Search and Unit Propagation Techniques

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

7777.mp4 7777.mp3

Universitat de Girona. Departament d鈥橧nform脿tica, Matem脿tica Aplicada i Estad铆stica

Other contributions: Universitat de Girona. Departament d鈥橧nform脿tica, Matem脿tica Aplicada i Estad铆stica
Author: Chen, Xiamin
Lei, Zhendong
Lu, Pinyan
Date: 2024 September 3
Abstract: 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
7777.mp4 7777.mp3
Format: audio/mpeg
video/mp4
Document access: http://hdl.handle.net/10256.1/7777
Language: eng
Publisher: Universitat de Girona. Departament d鈥橧nform脿tica, Matem脿tica Aplicada i Estad铆stica
Collection: 30th International Conference on Principles and Practice of Constraint Programming
Rights: Attribution-NonCommercial-ShareAlike 4.0 International
Rights URI: http://creativecommons.org/licenses/by-nc-sa/4.0/
Subject: Programaci贸 per restriccions (Inform脿tica) -- Congressos
Constraint programming (Computer science) -- Congresses
Optimitzaci贸 amb restriccions -- Congressos
Constrained optimization -- Congresses
Title: Deep Cooperation of Local Search and Unit Propagation Techniques
Type: info:eu-repo/semantics/lecture
Repository: DUGiMedia

Subjects

Authors