Please wait a minute...
Shopping Cart Email List Chinese
Advanced Search Fig/Tab
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Featured Articles  |  Most Downloaded  |  Most Reading
Online Submission Subscribe to Our RSS Content Feed
Front. Comput. Sci.    2024, Vol. 18 Issue (2) : 182326    https://doi.org/10.1007/s11704-023-3018-8
Artificial Intelligence
DeciLS-PBO: an effective local search method for pseudo-Boolean optimization
Luyu JIANG1,2, Dantong OUYANG1,2, Qi ZHANG1,2, Liming ZHANG1,2()
1. College of Computer Science and Technology, Jilin University, Changchun 130012, China
2. Key Laboratory of Symbolic Computation and Knowledge Engineering (Ministry of Education), Jilin University, Changchun 130012, China
 Download: PDF(1057 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Corresponding Author(s): Liming ZHANG   
Just Accepted Date: 14 June 2023   Issue Date: 09 August 2023
 Cite this article:   
Luyu JIANG,Dantong OUYANG,Qi ZHANG, et al. DeciLS-PBO: an effective local search method for pseudo-Boolean optimization[J]. Front. Comput. Sci., 2024, 18(2): 182326.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-023-3018-8
https://academic.hep.com.cn/fcs/EN/Y2024/V18/I2/182326
  
Instances #inst #variable #constraint
MWCB 24 974000?11381750 591827?10522608
WSNO 18 58580?2311113 214679?26701722
SAP 21 1650?11550 7756?108474
PB16 1600 2?400896 4?521620
Tab.1  The range of the number of variables and constraints for each kind of instance
Instances #inst DeciLS-PBO LS-PBO PBO-IHS
MWCB 24 22 2 0
WSNO 18 13 18 1
SAP 21 17 5 0
PB16 1600 1130 1045 1171
Total 1663 1182 1070 1172
Tab.2  Results of DeciLS-PBO and its competitors under 300 s time limit (value: #win)
Instances #inst DeciLS-PBO LS-PBO PBO-IHS
MWCB 24 22 2 0
WSNO 18 18 18 2
SAP 21 16 6 0
PB16 1600 1215 1142 1185
Total 1663 1271 1168 1187
Tab.3  Results of DeciLS-PBO and its competitors under 3600 s time limit (value: #win)
1 Z, Lei S, Cai C, Luo H Hoos . Efficient local search for pseudo Boolean optimization. In: Proceedings of the 24th International Conference on Theory and Applications of Satisfiability Testing. 2021, 332−348
2 Lei Z, Cai S, Luo C. Extended conjunctive normal form and an efficient algorithm for cardinality constraints. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence. 2020, 1141−1147
3 J, Berg E, Demirović P J Stuckey . Core-boosted linear search for incomplete MaxSAT. In: Proceedings of the 16th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 2019, 39−56
4 Elffers J, Nordstrom J. Divide and conquer: towards faster pseudo-Boolean solving. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. 2018, 1291−1299
5 R, Martins V, Manquinho I Lynce . Open-WBO: a modular MaxSAT solver. In: Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing. 2014, 438−445
6 Lei Z, Cai S. Solving (weighted) partial MaxSAT by dynamic local search for SAT. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. 2018, 1346−1352
7 P, Smirnov J, Berg M Järvisalo . Improvements to the implicit hitting set approach to pseudo-Boolean optimization. In: Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing. 2022, 13: 1−13: 18
[1] FCS-23018-OF-LJ_suppl_1 Download
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed