A new branch-and-bound algorithm for the maximum edge-weighted clique problem
San Segundo, Pablo; Coniglio, Stefano; Furini, Fabio; Ljubić, Ivana (2019), A new branch-and-bound algorithm for the maximum edge-weighted clique problem, European Journal of Operational Research, 278, 1, p. 76-90. 10.1016/j.ejor.2019.03.047
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
Author(s)San Segundo, Pablo
University of Southampton - Mathematical Sciences
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
ESSEC Business School
Abstract (EN)We study the maximum edge-weighted clique problem, a problem related to the maximum (vertex-weighted) clique problem which asks for finding a complete subgraph (i.e., a clique) of maximum total weight on its edges. The problem appears in a wide range of applications, including bioinformatics, material science, computer vision, robotics, and many more. In this work, we propose a new combinatorial branch-and-bound algorithm for the problem which relies on a novel bounding procedure capable of pruning a very large amount of nodes of the branch-and-bound tree. Extensive computational experiments on random and structured graphs, encompassing standard benchmarks used in the literature as well as recently introduced real-world large-scale graphs, show that our new algorithm outperforms the state-of-the-art by several orders of magnitude on many instances.
Subjects / KeywordsCombinatorial optimization; Branch-and-bound; Maximum edge-weighted clique problem
Showing items related by title and author.
Benders decomposition for very large scale partial set covering and maximal covering location problems Cordeau, Jean-François; Furini, Fabio; Ljubić, Ivana (2019) Article accepté pour publication ou publié