A Two-Stage MaxSAT Reasoning Approach for the Maximum Weight Clique Problem - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

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

(1) , (2, 3) , (4) , (5)
1
2
3
4
5

Résumé

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.
Fichier non déposé

Dates et versions

hal-03636425 , version 1 (10-04-2022)

Identifiants

  • HAL Id : hal-03636425 , version 1

Citer

Hua Jiang, Chu-Min Li, Yanli Liu, Felip Manya. A Two-Stage MaxSAT Reasoning Approach for the Maximum Weight Clique Problem. THIRTY-SECOND AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTIETH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / EIGHTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, Feb 2018, New-Orleans, United States. pp.1338-1346. ⟨hal-03636425⟩
23 Consultations
0 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More