True, they indeed do not contradict each other. I hadn't yet heard that there actually was an algorithm that could find optimal solutions, but I admit it's been a long time since I was interested in the issue.

Because of the time difference between generation a solution and generating the optimal solution, I'm guessing the algorithm bruteforces the optimal solutions, which explains part of the confusion: I was thinking about an algorithm that generates the optimal solution directly.