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; PMTK; gpuls-mwcp; CCLS; SCCWalk; BBMCSP; CCASat; H-Morph; G23FM; clusfind Cited in: 51 Publications all top 5 Cited by 93 Authors 8 Peng, Yuejian 7 Zhao, Cheng 6 Tang, Qingsong 5 Hao, Jin-Kao 4 Butenko, Sergiy I. 4 Wu, Qinghua 4 Zhang, Xiangde 3 Pardalos, Panos M. 3 Pullan, Wayne 2 Balasundaram, Balabhaskar 2 Busygin, Stanislav 2 Cai, Shaowei 2 Chang, Yanming 2 Glover, Fred W. 2 Pelillo, Marcello 1 Andonov, Rumen A. 1 Bai, Zhanhua 1 Bandyopadhyay, Sanghamitra 1 Barbosa, Valmir Carneiro 1 Bhattacharyya, Malay 1 Botella, Arnaud 1 Campos, Luciana C. D. 1 Caumon, Guillaume 1 Chen, Jiejiang 1 Cook, William John 1 Dai, Jinyu 1 Dang, Duc-Cuong 1 Fontes, Dalila B. M. M. 1 Geng, Xiutang 1 Goëffon, Adrien 1 Gomes, Fernando C. 1 Gould, Nicholas Ian Mark 1 Grosso, Andrea 1 Gruzdeva, Tat’yana Vladimirovna 1 Gu, Ran 1 Gualandi, Stefano 1 Gupta, Ashok Kumar 1 Gvozdenović, Nebojša 1 Hazan, Elad 1 Held, Stephan 1 Hicks, Illya V. 1 Hoos, Holger H. 1 Hosseinian, Seyedmohammadhossein 1 Jiang, Baoping 1 Karimi, Hamid Reza 1 Koren, Tomer 1 Laurent, Monique 1 Letchford, Adam N. 1 Levi, Amit 1 Levy, Bruno 1 Li, Xueliang 1 Locatelli, Marco 1 Lu, Guangquan 1 Lu, Qiang 1 Lü, Zhipeng 1 Malod-Dognin, Noël 1 Malucelli, Federico 1 McClosky, Benjamin 1 Meneses, Cláudio N. 1 Montemanni, Roberto 1 Moukrim, Aziz 1 Pan, Linqiang 1 Pištěk, Miroslav 1 Rebennack, Steffen 1 Régin, Jean-Charles 1 Reinelt, Gerhard 1 Robinson, Daniel P. 1 Rossi, Fabrizio 1 Rota Bulò, Samuel 1 Sattar, Abdul 1 Sewell, Edward C. 1 Shi, Yongtang 1 Singh, Alok Kumar 1 Smith, Derek H. 1 Smriglio, Stefano 1 Su, Kaile 1 Sun, YanPing 1 Thorne, H. Sue 1 Torsello, Andrea 1 Trukhanov, Svyatoslav 1 Viana, Gerardo Valdisio R. 1 Wang, Guoren 1 Wang, Yang 1 Wang, Yiyuan 1 Wu, Zhengtian 1 Xia, Xiaoyan 1 Xiao, Jianhua 1 Xu, Jin 1 Yanev, Nicola 1 Yao, Yuping 1 Yin, Minghao 1 Yoshida, Yuichi 1 Zhou, Yi all top 5 Cited in 27 Serials 12 Journal of Combinatorial Optimization 3 Journal of Global Optimization 3 Journal of Heuristics 2 Artificial Intelligence 2 Information Sciences 2 Journal of Optimization Theory and Applications 2 Computers & Operations Research 2 European Journal of Operational Research 2 Mathematical Programming. Series A. Series B 2 Mathematical Programming Computation 1 Discrete Applied Mathematics 1 Journal of the Franklin Institute 1 Kybernetika 1 Bulletin of the Korean Mathematical Society 1 Acta Mathematicae Applicatae Sinica. English Series 1 Graphs and Combinatorics 1 Annals of Operations Research 1 Neural Computation 1 Designs, Codes and Cryptography 1 The Journal of Artificial Intelligence Research (JAIR) 1 International Transactions in Operational Research 1 INFORMS Journal on Computing 1 Computational Geosciences 1 Journal of Software 1 Discrete Optimization 1 Optimization Letters 1 Serdica Journal of Computing all top 5 Cited in 9 Fields 42 Operations research, mathematical programming (90-XX) 23 Combinatorics (05-XX) 10 Computer science (68-XX) 3 Biology and other natural sciences (92-XX) 2 Numerical analysis (65-XX) 2 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 Information and communication theory, circuits (94-XX) 1 Geophysics (86-XX) 1 Systems theory; control (93-XX) Citations by Year