Using SVM to combine global heuristics for the Standard Quadratic Problem

作者：Dellepiane Umberto^*; Palagi Laura

来源：European Journal of Operational Research, 2015, 241(3): 596-605.

DOI：10.1016/j.ejor.2014.09.054

• Quadratic programming
• Nonlinear programming
• Data mining
• Maximum Clique Problem
• Global optimization

The Standard Quadratic Problem (StQP) is an NP-hard problem with many local minimizers (stationary points). In the literature, heuristics based on unconstrained continuous non-convex formulations have been proposed (Bomze & Palagi, 2005; Bomze, Grippo, & Palagi, 2012) but none dominates the other in terms of best value found. Following (Cassioli, DiLorenzo, Locatelli, Schoen, & Sciandrone, 2012) we propose to use Support Vector Machines (SVMs) to define a multistart global strategy which selects the "best" heuristic. We test our method on StQP arising from the Maximum Clique Problem on a graph which is a challenging combinatorial problem. We use as benchmark the clique problems in the DIMACS challenge.

• 出版日期2015-3-16