Ítem


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’Informàtica, Matemàtica Aplicada i Estadística

Altres contribucions: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Autor: Chen, Xiamin
Lei, Zhendong
Lu, Pinyan
Data: 3 setembre 2024
Resum: 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
Accés al document: http://hdl.handle.net/10256.1/7777
Llenguatge: eng
Editor: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Col·lecció: 30th International Conference on Principles and Practice of Constraint Programming
Drets: Attribution-NonCommercial-ShareAlike 4.0 International
URI Drets: http://creativecommons.org/licenses/by-nc-sa/4.0/
Matèria: Programació per restriccions (Informàtica) -- Congressos
Constraint programming (Computer science) -- Congresses
Optimització amb restriccions -- Congressos
Constrained optimization -- Congresses
Títol: Deep Cooperation of Local Search and Unit Propagation Techniques
Tipus: info:eu-repo/semantics/lecture
Repositori: DUGiMedia

Matèries

Autors