[jacquesm]

NP hard for a pathological case doesn't mean all practical cases are pathological. Many of the cases have optimal solutions in a reasonable amount of time without resorting to brute force because you can use structure in the dataset to limit the search space.

That you can construct a pathological case makes something NP hard for an arbitrary case but not for all cases. Compare with QS: it's very fast for most practical cases but you can construct a case where it performs quite bad, much worse than you'd expect given the name. But in practice that isn't all that relevant.