A nonconvex quadratic optimization approach to the maximum edge weight clique problem

• Tipo: Artigo em Revista Científica Internacional
• Data: 2018

Autores

Hosseinian, S (Autor) Outra; Dalila B.M.M. Fontes (Autor) FEP; Butenko, S (Autor) Outra

Revista

Título: Journal of Global Optimization

Vol. 72

Páginas: 219-240

ISSN: 0925-5001

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 11 Citações

Scopus - 11 Citações

Outras Informações

ID Authenticus: P-00N-QCP

DOI: 10.1007/s10898-018-0630-5

Abstract (EN): The maximum edge weight clique (MEWC) problem, defined on a simple edge-weighted graph, is to find a subset of vertices inducing a complete subgraph with the maximum total sum of edge weights. We propose a quadratic optimization formulation for the MEWC problem and study characteristics of this formulation in terms of local and global optimality. We establish the correspondence between local maxima of the proposed formulation and maximal cliques of the underlying graph, implying that the characteristic vector of a MEWC in the graph is a global optimizer of the continuous problem. In addition, we present an exact algorithm to solve the MEWC problem. The algorithm is a combinatorial branch-and-bound procedure that takes advantage of a new upper bound as well as an efficient construction heuristic based on the proposed quadratic formulation. Results of computational experiments on some benchmark instances are also presented.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 22