DROPS

Document

DOI: 10.4230/LIPIcs.CP.2023.41

Improving Local Search for Pseudo Boolean Optimization by Fragile Scoring Function and Deep Optimization

Authors: Wenbo Zhou, Yujiao Zhao, Yiyuan Wang, Shaowei Cai, Shimao Wang, Xinyu Wang, and Minghao Yin

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

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.

Cite as

Wenbo Zhou, Yujiao Zhao, Yiyuan Wang, Shaowei Cai, Shimao Wang, Xinyu Wang, and Minghao Yin. Improving Local Search for Pseudo Boolean Optimization by Fragile Scoring Function and Deep Optimization. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 41:1-41:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.CP.2023.41},
  URN =		{urn:nbn:de:0030-drops-190784},
  doi =		{10.4230/LIPIcs.CP.2023.41},
  annote =	{Keywords: Local Search, Pseudo-Boolean Optimization, Deep Optimization}
}

Search Results

Documents authored by Wang, Shimao

Improving Local Search for Pseudo Boolean Optimization by Fragile Scoring Function and Deep Optimization

Abstract

Cite as

Thanks for your feedback!

Could not send message