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

Seyedmohammadhossein Hosseinian (), Dalila B. M. M. Fontes () and Sergiy Butenko ()
Additional contact information
Seyedmohammadhossein Hosseinian: Texas A&M University
Dalila B. M. M. Fontes: Universidade do Porto
Sergiy Butenko: Texas A&M University

Journal of Global Optimization, 2018, vol. 72, issue 2, No 4, 219-240

Abstract: Abstract 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.

Keywords: Maximum edge weight clique problem; Quadratic optimization; Continuous approaches to discrete problems (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-018-0630-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:72:y:2018:i:2:d:10.1007_s10898-018-0630-5

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-018-0630-5

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().