Article ID: | iaor20122801 |
Volume: | 52 |
Issue: | 3 |
Start Page Number: | 537 |
End Page Number: | 551 |
Publication Date: | Mar 2012 |
Journal: | Journal of Global Optimization |
Authors: | Dr Mirjam, Sponsel Julia, Bundfuss Stefan |
Keywords: | programming: quadratic, matrices, combinatorial optimization, programming: branch and bound |
Copositivity plays a role in combinatorial and nonconvex quadratic optimization. However, testing copositivity of a given matrix is a co‐NP‐complete problem. We improve a previously given branch‐and‐bound type algorithm for testing copositivity and discuss its behavior in particular for the maximum clique problem. Numerical experiments indicate that the speedup is considerable.