QUALEX
swMATH ID: | 4742 |
Software Authors: | Busygin, Stanislav |
Description: | A new trust region technique for the maximum weight clique problem A new simple generalization of the Motzkin-Straus theorem for the maximum weight clique problem is formulated and directly proved. Within this framework a trust region heuristic is developed. In contrast to usual trust region methods, it regards not only the global optimum of a quadratic objective over a sphere, but also a set of other stationary points of the program. We formulate and prove a condition when a Motzkin-Straus optimum coincides with such a point. The developed method has complexity O(n 3 ), where n is the number of vertices of the graph. It was implemented in a publicly available software package QUALEX-MS. Computational experiments indicate that the algorithm is exact on small graphs and very efficient on the DIMACS benchmark graphs and various random maximum weight clique problem instances |
Homepage: | http://www.stasbusygin.org/ |
Keywords: | maximum weight clique; Motzkin-Straus theorem; quadratic programming; heuristic; trust region |
Related Software: | DIMACS; Max-AO; Tabu search; BHOSLIB; GQTPAR; MaxCliqueDyn; EXTRACOL; Algorithm 787; NuMVC; HSL-VF05; Hyperheuristics; QPLIB; BARON; Gurobi; Mathematica; PMTK; gpuls-mwcp; BBMCSP; CCLS; SCCWalk |
Cited in: | 54 Documents |
all
top 5
Cited by 99 Authors
all
top 5
Cited in 28 Serials
all
top 5