Mathematicians have been working on the so-called traveling salesman problem — what’s the shortest itinerary a salesman can follow to visit all the stops on his route? — for a long time, largely because it maps to so many other common problems. “Applications range from scheduling cable-TV service calls and routing parcel-delivery trucks to drilling holes in a circuit board, where you want to minimize how far the drill, like the salesman, must travel.” Did You Hear the One About the Salesman Who Traveled Better? also cites this interesting application:
An algorithm he developed for ILOG, which sells algorithm-packed custom software, tackled the National Football League’s 2004 schedule. He had to juggle 256 games among 32 teams, subject to multiple constraints. There had to be a nationally appealing game every Monday night and at least one must-see match-up every Sunday, for example, and he couldn’t send a team on the road for weeks at a time.Dr. Lustig’s algorithm created thousands of schedules that fit these constraints in a fraction of the time it took by trial-and-error computing. Even better, it can tweak a schedule in less than a day if, say, the NFL decides that a Giants-Redskins game simply won’t do for Week 8 (it’s Week 2). In the past, making that change would produce a domino effect taking days to fix.
Many of the new algorithms rely on the interior-point method:
A linear programming method that achieves optimization by going through the middle of the solid defined by the problem rather than around its surface.A polynomial time linear programming algorithm using an interior point method was found by Karmarkar (1984). Arguably, interior point methods were known as early as the 1960s in the form of the barrier function methods, but the media hype accompanying Karmarkar’s announcement led to these methods receiving a great deal of attention. However, it should be noted that while Karmarkar claimed that his implementation was much more efficient than simplex method, the potential of interior point method was established only later. By 1994, there were over 1300 published papers on interior point methods. Current efficient implementations are mostly based on Mehrotra’s predictor-corrector technique, where the Cholesky decomposition of the normal equation is used to perform the Newton iteration, together with some heuristics to estimate the penalty parameter. All current interior point methods implementations rely heavily on having very efficient code for sparse Cholesky decomposition.
I may have to break out my old linear programming text…and read a few new papers.