NuDist: An Efficient Local Search Algorithm for (Weighted) Partial MaxSAT. (15th August 2019)
- Record Type:
- Journal Article
- Title:
- NuDist: An Efficient Local Search Algorithm for (Weighted) Partial MaxSAT. (15th August 2019)
- Main Title:
- NuDist: An Efficient Local Search Algorithm for (Weighted) Partial MaxSAT
- Authors:
- Lei, Zhendong
Cai, Shaowei - Abstract:
- Abstract: Maximum satisfiability (MaxSAT) is the optimization version of the satisfiability (SAT). Partial MaxSAT (PMS) generalizes SAT and MaxSAT by introducing hard and soft clauses, while Weighted PMS (WPMS) is the weighted version of PMS where each soft clause has a weight. These two problems have many important real-world applications. Local search is a popular method for solving (W)PMS. Recently, significant progress has been made in this direction by tailoring local search for (W)PMS, and a representative algorithm is the Dist algorithm. In this paper, we propose two ideas to improve Dist, including a clause-weighting scheme and a variable-selection heuristic. The resulting algorithm is called NuDist. Extensive experiments on PMS and WPMS benchmarks from the MaxSAT Evaluations (MSE) 2016 and 2017 show that NuDist significantly outperforms state-of-the-art local search solvers and performs better than state-of-the-art complete solvers including Open-WBO and WPM3 on MSE 2017 benchmarks. Also, empirical analyses confirm the effectiveness of the proposed ideas.
- Is Part Of:
- Computer journal. Volume 63:Number 9(2020)
- Journal:
- Computer journal
- Issue:
- Volume 63:Number 9(2020)
- Issue Display:
- Volume 63, Issue 9 (2020)
- Year:
- 2020
- Volume:
- 63
- Issue:
- 9
- Issue Sort Value:
- 2020-0063-0009-0000
- Page Start:
- 1321
- Page End:
- 1337
- Publication Date:
- 2019-08-15
- Subjects:
- local search -- partial maximum satisfiability
Computers -- Periodicals
005.1 - Journal URLs:
- http://comjnl.oxfordjournals.org/ ↗
http://ukcatalogue.oup.com/ ↗ - DOI:
- 10.1093/comjnl/bxz063 ↗
- Languages:
- English
- ISSNs:
- 0010-4620
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3394.060000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 15069.xml