Article ID: | iaor20123776 |
Volume: | 20 |
Issue: | 1 |
Start Page Number: | 35 |
End Page Number: | 51 |
Publication Date: | Apr 2012 |
Journal: | TOP |
Authors: | Grippo Luigi, Palagi Laura, Bomze Immanuel |
Keywords: | graphs, heuristics |
A standard quadratic optimization problem (StQP) consists of finding the largest or smallest value of a (possibly indefinite) quadratic form over the standard simplex which is the intersection of a hyperplane with the positive orthant. This NP‐hard problem has several immediate real‐world applications like the Maximum Clique Problem, and it also occurs in a natural way as a subproblem in quadratic programming with linear constraints. We propose unconstrained reformulations of StQPs, by using different approaches. We test our method on clique problems from the DIMACS challenge.