Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Effective Approaches to Solve P-Center Problem via Set Covering and SAT

Abstract : The classic p-center problem consists of choosing a set of p vertices in an undirected graph as facilities in order to minimize the maximum distance between each client vertex and its closest facility. The problem is equivalent to covering all vertices by no more than p circles with the smallest possible radius, which can be tackled by solving a series of the decision version of set covering subproblems with the same cardinality constraint (<= p) and gradually decreasing the covering radius. In this paper, we solve the p-center problem via set covering and SAT. We first transform the p-center problem into a series of set covering subproblems and simplify them by some reduction rules. Then, we present two kinds of encoding methods to convert them into CNF format and solve them with several state-of-the-art SAT solvers. Tested on three sets of totally 70 benchmark instances, our proposed approach can improve the previous best known results for 3 instances using the heuristic SAT solvers while proving the optimality for 59 instances using the exact SAT solvers. The computational results demonstrate the effectiveness of the proposed approach in terms of both solution quality and computational efficiency. In addition, the main advantage of our approach is twofold: The independence of the subproblems allows the problem to be solved in parallel; The approach to transform the original problem into SAT is fiexible such that various state-of-the-art SAT solvers can be used.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03636417
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:13
Dernière modification le : vendredi 5 août 2022 - 11:22:18

Lien texte intégral

Identifiants

Collections

Citation

Xiaolu Liu, Yuan Fang, Jiaming Chen, Zhouxing Su, Chumin Li, et al.. Effective Approaches to Solve P-Center Problem via Set Covering and SAT. IEEE Access, IEEE, 2020, 8, pp.161232-161244. ⟨10.1109/ACCESS.2020.3018618⟩. ⟨hal-03636417⟩

Partager

Métriques

Consultations de la notice

17