A new simple generalization of the Motzkin-Straus theorem for the maximum weight clique problem is formulated and directly proved. Within this framework a new 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 graph vertices. It was implemented in a publicly available software package QUALEX-MS. Computational experiments evidence that the algorithm is exact on small graphs and exceptionally efficient on DIMACS benchmark graphs and various random maximum weight clique problem instances.
Citation
Submitted to Special Issue of Discrete Applied Mathematics: Combinatorial Optimization 2002.
Article
View A New Trust Region Technique for the Maximum Weight Clique Problem