期刊
JOURNAL OF GLOBAL OPTIMIZATION
卷 72, 期 2, 页码 219-240出版社
SPRINGER
DOI: 10.1007/s10898-018-0630-5
关键词
Maximum edge weight clique problem; Quadratic optimization; Continuous approaches to discrete problems
资金
- DOD-ONR [N00014-13-1-0635]
- NSF [CMMI-1538493]
- [SFRH/BSAB/113662/2015]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据