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

Hua Jiang; Chu-Min Li; Yanli Liu; Felip Manya

Communication dans un congrès

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

Hua Jiang ¹ Chu-Min Li ^{2, 3} Yanli Liu ⁴ Felip Manya ⁵

1 UCCS - University of Colorado [Colorado Springs]

2 COALA - COntraintes, ALgorithmes et Applications

LIS - Laboratoire d'Informatique et Systèmes

3 MIS - Modélisation, Information et Systèmes - UR UPJV 4290

4 College of Computer Science [Chengdu]

5 IIIA / CSIC - Artificial Intelligence Research Institute / Spanish Scientific Research Council

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.

Type de document :

Communication dans un congrès

Domaine :

Informatique [cs]

Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03636425
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:21
Dernière modification le : lundi 11 avril 2022 - 03:31:05

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

Identifiants

Collections

Citation

Exporter

Métriques

20

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

Identifiants

Collections

Citation

Exporter

Partager

Métriques

20