If you define "solve" as getting right answer always, then they don't solve the problem per se. But by your definition above (and I agree with it), they do give an answer for all instances, except that sometimes the answer may not be optimal. But that's alright. Life can suck occasionally, as long as it doesn't suck constantly to the point of hopelessness :)