|
Can look at the now old work of G. Nemhauser. His work was for combinatorial optimization and not just for exactly the traveling salesman problem (TSP). E.g., there is George L. Nemhauser and
Laurence A. Wolsey,
Integer and Combinatorial Optimization,
ISBN 0-471-35943-2,
John Wiley & Sons, Inc.,
New York,
1999. Some approaches involve set covering and set partitioning. Soooo, for the FedEx fleet, first just generate all single airplane feasible tours from the Memphis hub and back. Here can honor some really goofy constraints and complicated costing; can even handle some stochastic issues, i.e., the costs depend on the flight planning and that depends on the loads which are random, but it would be okay to work with just expectations -- we're talking complicated costing! Then with all those tours generated, pick ones that cover all the cities to be served, i.e., partition the cities. Have a good shot at using linear programming, tweaked a little to handle 0-1 constraints, to pick the tours. Then more generally for a lot of practical problems can write linear programming problems with some of the variables integer. Then can tweak the simplex algorithm of linear programming to handle some of such constraints fairly naturally in the algorithm. E.g., of course, can proceed with now classic branch and bound. The TSP taken narrowly can be regarded as more specialized. So, net, there is a big bag of essentially tricks, some with some math and some just heuristics. Part of the interest in the issue of P versus NP was to do away with the bag of tricks and have just some one grand, fantastic algorithm and computer program with guaranteed performance. Nice if doable. Alas, after all these years, so far not really "doable", not as just one grand, fantastic .... And the question of P versus NP has resisted so much for so long that it has even a philosophical flavor. And there are serious claims that a technically good algorithm would have some really astounding consequences. Sure, I have some half baked ideas sitting around that I hope will show that P = NP -- doesn't everyone? But my point here was just simple: For several decades we have been able to do quite well on real problems. Oh, for the problem with 600,000 0-1 variables and 40,000 contraints, otherwise linear, I used nonlinear duality theory (which is simple) or, if you wish, Lagrangian relaxation -- it's one of the tricks. Another old trick: For the actual TSP in any Euclidean space (sure, the plane but also 3 dimensions or 50 if you want), that is, with Euclidean distance, just find a minimum spanning tree (there are at least two good, that is, polynomial algorithms, for that) and then in a simple and fairly obvious way make a TSP tour out of that tree. That approach actually has some probabilistic bounds on how close it is to optimality, and it does better with more cities -- it's another tool in the kit. My main conclusion about the TSP, combinatorial optimization, and optimization more generally is that there are way, Way, WAY too few good customers. Whether there is 15% of project cost to be saved or not, the people responsible for the projects just do NOT want to be bothered. In simple terms, in practice, it is essentially a dead field. My view is that suggesting that a young person devote some significant part of their career to optimization is, bluntly, in a word, irresponsible. |