Continuous cubic formulations for cluster detection problems in networks

• 成果类型: Article
• 署名作者: Stozhkov, Vladimir; Buchanan, Austin; Butenko, Sergiy; Boginski, Vladimir
• 署名单位: Oklahoma State University System; Oklahoma State University - Stillwater; Texas A&M University System; Texas A&M University College Station; State University System of Florida; University of Central Florida
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01572-4
• 发表日期: 2022
• 页码: 279-307
• 关键词: global optimization; clique; graph; algorithms; approximation; search; number; bounds

摘要

The celebrated Motzkin-Straus formulation for the maximum clique problem provides a nontrivial characterization of the clique number of a graph in terms of the maximum value of a nonconvex quadratic function over a standard simplex. It was originally developed as a way of proving Turan's theorem in graph theory, but was later used to develop competitive algorithms for the maximum clique problem based on continuous optimization. Clique relaxations, such ass-defective clique ands-plex, emerged as attractive, more practical alternatives to cliques in network-based cluster detection models arising in numerous applications. This paper establishes continuous cubic formulations for the maximums-defective clique problem and the maximums-plex problem by generalizing the Motzkin-Straus formulation to the corresponding clique relaxations. The formulations are used to extend Turan's theorem and other known lower bounds on the clique number to the considered clique relaxations. Results of preliminary numerical experiments with the CONOPT solver demonstrate that the proposed formulations can be used to quickly compute high-quality solutions for the maximums-defective clique problem and the maximums-plex problem. The proposed formulations can also be used to generate interesting test instances for global optimization solvers.