Institutional Repository
| Tailoring local search for partial MaxSAT | |
| Cai, Shaowei (1); Luo, Chuan (3); Thornton, John (4); Su, Kaile (4); Cai, Shaowei | |
| 2014 | |
| Conference Name | 28th AAAI Conference on Artificial Intelligence, AAAI 2014, 26th Innovative Applications of Artificial Intelligence Conference, IAAI 2014 and the 5th Symposium on Educational Advances in Artificial Intelligence, EAAI 2014 |
| Pages | 2623-2629 |
| Conference Date | July 27, 2014 - July 31, 2014 |
| Conference Place | Quebec City, QC, Canada |
| Indexed Type | EI |
| Publish Place | AI Access Foundation |
| ISBN | 9781577356806 |
| Department | (1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China; (2) Queensland Research Laboratory, NICTA, Brisbane, Australia; (3) Key Laboratory of High Confidence Software Technologies, Peking University, Beijing, China; (4) Institute for Integrated and Intelligent Systems, Griffith University, Brisbane, Australia |
| English Abstract | Partial MaxSAT (PMS) is a generalization to SAT and MaxSAT. Many real world problems can be encoded into PMS in a more natural and compact way than SAT and MaxSAT. In this paper, we propose new ideas for local search for PMS, which mainly rely on the distinction between hard and soft clauses. We use these ideas to develop a local search PMS algorithm called Dist. Experimental results on PMS benchmarks from MaxSAT Evaluation 2013 show that Dist significantly outperforms state-of-the-art PMS algorithms, including both local search algorithms and complete ones, on random and crafted benchmarks. For the industrial benchmark, Dist dramatically outperforms previous local search algorithms and is comparable with complete algorithms.; Partial MaxSAT (PMS) is a generalization to SAT and MaxSAT. Many real world problems can be encoded into PMS in a more natural and compact way than SAT and MaxSAT. In this paper, we propose new ideas for local search for PMS, which mainly rely on the distinction between hard and soft clauses. We use these ideas to develop a local search PMS algorithm called Dist. Experimental results on PMS benchmarks from MaxSAT Evaluation 2013 show that Dist significantly outperforms state-of-the-art PMS algorithms, including both local search algorithms and complete ones, on random and crafted benchmarks. For the industrial benchmark, Dist dramatically outperforms previous local search algorithms and is comparable with complete algorithms. |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/16611 |
| Collection | 中国科学院软件研究所 |
| Corresponding Author | Cai, Shaowei |
| Recommended Citation GB/T 7714 | Cai, Shaowei ,Luo, Chuan ,Thornton, John ,et al. Tailoring local search for partial MaxSAT[C]. AI Access Foundation,2014:2623-2629. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment