Something being NP-hard doesn't preclude algorithms that solve or sufficiently approximate solutions for instances that occur in practice. SAT is also NP-hard, but you can download solvers that can handle most huge instances you need solved just fine.
The question isn't "How can you do possibly well on NP-hard problems?" It's, what particular tricks are these people using that allow them to get around the NP-hardness of this particular problem? The article doesn't talk about that and it should.
