Software Search - zbMATH Open

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; HSL-VF05; Hyperheuristics; PMTK; gpuls-mwcp; CCLS; SCCWalk; BBMCSP; CCASat; NuMVC; H-Morph; G23FM; clusfind
Referenced in:	50 Publications

all top 5

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	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	Koren, Tomer
1	Laurent, Monique
1	Letchford, Adam N.
1	Levi, Amit
1	Levy, Bruno
1	Li, Xueliang
1	Locatelli, Marco
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	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

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	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

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)
1	Geophysics (86-XX)
1	Information and communication theory, circuits (94-XX)