A Two-Stage MaxSAT Reasoning Approach for the Maximum Weight Clique Problem

Authors

  • Hua Jiang Jianghan University, College of Math and Computer Science
  • Chu-Min Li MIS, Universite ́ de Picardie Jules Verne
  • Yanli Liu Huazhong University of Science and Technology
  • Felip Manyà Artificial Intelligence Research Institute (IIIA, CSIC)

DOI:

https://doi.org/10.1609/aaai.v32i1.11527

Keywords:

Maximum Weight Clique Problem, MaxSAT Reasoning, Branch-and-Bound

Abstract

MaxSAT reasoning is an effective technology used in modern branch-and-bound (BnB) algorithms for the Maximum Weight Clique problem (MWC) to reduce the search space. However, the current MaxSAT reasoning approach for MWC is carried out in a blind manner and is not guided by any relevant strategy. In this paper, we describe a new BnB algorithm for MWC that incorporates a novel two-stage MaxSAT reasoning approach. In each stage, the MaxSAT reasoning is specialised and guided for different tasks. Experiments on an extensive set of graphs show that the new algorithm implementing this approach significantly outperforms relevant exact and heuristic MWC algorithms in both small/medium and massive real-world graphs.

AAAI 2018 Proceedings Cover

Downloads

Published

2018-04-25

How to Cite

Jiang, H., Li, C.-M., Liu, Y., & Manyà, F. (2018). A Two-Stage MaxSAT Reasoning Approach for the Maximum Weight Clique Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.11527

Issue

Vol. 32 No. 1 (2018): Thirty-Second AAAI Conference on Artificial Intelligence

Section

AAAI Technical Track: Heuristic Search and Optimization