License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.41
URN: urn:nbn:de:0030-drops-190784
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19078/
Zhou, Wenbo ;
Zhao, Yujiao ;
Wang, Yiyuan ;
Cai, Shaowei ;
Wang, Shimao ;
Wang, Xinyu ;
Yin, Minghao
Improving Local Search for Pseudo Boolean Optimization by Fragile Scoring Function and Deep Optimization
Abstract
Pseudo-Boolean optimization (PBO) is usually used to model combinatorial optimization problems, especially for some real-world applications. Despite its significant importance in both theory and applications, there are few works on using local search to solve PBO. This paper develops a novel local search framework for PBO, which has three main ideas. First, we design a two-level selection strategy to evaluate all candidate variables. Second, we propose a novel deep optimization strategy to disturb some search spaces. Third, a sampling flipping method is applied to help the algorithm jump out of local optimum. Experimental results show that the proposed algorithms outperform three state-of-the-art PBO algorithms on most instances.
BibTeX - Entry
@InProceedings{zhou_et_al:LIPIcs.CP.2023.41,
author = {Zhou, Wenbo and Zhao, Yujiao and Wang, Yiyuan and Cai, Shaowei and Wang, Shimao and Wang, Xinyu and Yin, Minghao},
title = {{Improving Local Search for Pseudo Boolean Optimization by Fragile Scoring Function and Deep Optimization}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {41:1--41:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-300-3},
ISSN = {1868-8969},
year = {2023},
volume = {280},
editor = {Yap, Roland H. C.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19078},
URN = {urn:nbn:de:0030-drops-190784},
doi = {10.4230/LIPIcs.CP.2023.41},
annote = {Keywords: Local Search, Pseudo-Boolean Optimization, Deep Optimization}
}
