Solving Set Cover and Dominating Set via Maximum Satisfiability

Authors

  • Zhendong Lei Chinese Academy of Sciences
  • Shaowei Cai Chinese Academy of Sciences

DOI:

https://doi.org/10.1609/aaai.v34i02.5517

Abstract

The Set Covering Problem (SCP) and Dominating Set Problem (DSP) are NP-hard and have many real world applications. SCP and DSP can be encoded into Maximum Satisfiability (MaxSAT) naturally and the resulting instances share a special structure. In this paper, we develop an efficient local search solver for MaxSAT instances of this kind. Our algorithm contains three phrase: construction, local search and recovery. In construction phrase, we simplify the instance by three reduction rules and construct an initial solution by a greedy heuristic. The initial solution is improved during the local search phrase, which exploits the feature of such instances in the scoring function and the variable selection heuristic. Finally, the corresponding solution of original instance is recovered in the recovery phrase. Experiment results on a broad range of large scale instances of SCP and DSP show that our algorithm significantly outperforms state of the art solvers for SCP, DSP and MaxSAT.

Downloads

Published

2020-04-03

How to Cite

Lei, Z., & Cai, S. (2020). Solving Set Cover and Dominating Set via Maximum Satisfiability. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1569-1576. https://doi.org/10.1609/aaai.v34i02.5517

Issue

Section

AAAI Technical Track: Constraint Satisfaction and Optimization