×

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

8 Peng, Yuejian
8 Zhao, Cheng
7 Tang, Qingsong
6 Butenko, Sergiy I.
5 Hao, Jin-Kao
5 Zhang, Xiangde
4 Wu, Qinghua
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 Boginski, Vladimir L.
1 Botella, Arnaud
1 Buchanan, Austin
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 Makovenko, Mykyta
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 Pardalos, Miltiades P.
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
1 Smith, Derek H.
1 Smriglio, Stefano
1 Stozhkov, Vladimir
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, Nikola Ivanov
1 Yao, Yuping
1 Yin, Minghao
1 Yoshida, Yuichi
1 Zhao, Peng
1 Zhou, Yi
all top 5

Cited in 28 Serials

12 Journal of Combinatorial Optimization
4 Journal of Global Optimization
3 Mathematical Programming. Series A. Series B
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 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 SIAM Journal on Optimization
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 10 Fields

45 Operations research, mathematical programming (90-XX)
26 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 Linear and multilinear algebra; matrix theory (15-XX)
1 Geophysics (86-XX)
1 Systems theory; control (93-XX)

Citations by Year