News for hackers. Stuff that matters.
Re:After almost 20 years, math problem falls by archangel_one on Tuesday July 19, 2011 @06:04AM (#2780201)
I would expect an airline routing problem to be an integer program (because you can't send 2/3 of an aeroplane along one route and 1/3 along another), and integer programming is NP-hard. On the bright side, at all times you have an estimate of the best possible solution so you can terminate early when you're within some percentage (say 1%) of optimal.

Interestingly they still use the simplex method repeatedly during the branch-and-bound solving process, because it only requires a little work to adjust at each step, whereas the methods with guaranteed polynomial worst case tend to take that polynomial time regardless of how "close" they start to the optimum. So, as you say, convential complexity analysis suggests that simplex would be an awful lot less useful than it is.

There are no comments on this comment yet.