It has recently been shown that linear programs over the cone of completely positive matrices give exact formulations for many NP-hard combinatorial optimization problems. This motivates the investigation of solution methods for such problems. In this talk I will present a heuristic algorithm for this problem, whos main effort in each iteration consists in solving a convex quadratic problem in sign constrained variables. The algorithm will be applied to random copositive programs as well as to the copositive formulation of some NP-hard graph optimization problems. (joint work with M. Bomze (Vienna) and F. Jarre (Duesseldorf))