Using SVM to combine global heuristics for the Standard Quadratic Problem

Umberto Dellepiane and Laura Palagi

European Journal of Operational Research, 2015, vol. 241, issue 3, 596-605

Abstract: 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.

Keywords: Quadratic programming; Nonlinear programming; Data mining; Maximum Clique Problem; Global optimization (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221714007930
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:241:y:2015:i:3:p:596-605

DOI: 10.1016/j.ejor.2014.09.054

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().