Obviously it depends a whole lot on the scale. They gave some idea of number of constraints required to be satisfied, but it's not clear to me what the actual constraints were. I think it's not outrageous that on scan it might have sounded intractable.

Practical here means: Occurs in practice. And that they are optimally solvable in practice is not a tautology. It could be that you would need human insight (like you still need for most proving interesting mathematical theorems), or that people would only solve approximations. (People do solve approximations, too.)