Tag Archives: TSP

punk rock OR featured on math podcast “The Other Half”

One of my blog posts about starting a fire at a gas station was featured on the math podcast The Other Half called “The Road Trip” by podcasters and professors Dr. Annie Rorem and Dr. Anna Haensch [Listen here] The podcast is about taking an optimal road trip (the Traveling Salesman Problem (TSP)) and rare risks associated with travel.

In The Road Trip, Anna and Annie look into the math that undergirds the great American summertime tradition of rolling down the windows, turning up the stereo, and touring the countryside by automobile.

Randy Olson has made the planning part easy by computing the optimal road trip across the U.S. His work to minimize the miles between landmarks in the lower 48 has been featured in the Washington Post and on Discovery News. In fact, Tracy Staedter of Discovery News can be credited not only with encouraging Olson to tackle this problem, but also with determining the list of landmarks he used. If you have a road trip you’d like to optimize, check out his code here.

And, because cars don’t run on math alone, we also consider the necessity of refueling on the road. In particular, we ask Laura McLay to weigh in on gas station safety, as she computes the conditional probability of blowing yourself up while you’re pumping gas.

The Road Trip” is n excellent podcast! Thanks to Annie and Anna for doing such a great job and for being math ambassadors. I look forward to future episodes.

The Other Half is part of ACME Science, which offers several other math and science podcasts.

One thing I would like to add to the podcast is that there are real applications of the TSP and risk analysis. We academics don’t always sit up in our ivory towers coming up with silly problems to solve that are divorced from the real world. We need to be able to characterize rare risks for numerous applications (e.g., nuclear power risks) and then communicate those risks to others for managing rare but potentially catastrophic risks. I have a few links to related blog posts at the bottom of this post. Likewise, the TSP isn’t just used to plan summer road trips. It’s used by trucking and delivery companies to plan routes, in gene sequencing, for meals-on-wheels deliveries, and in emergency response after a disaster.

A second point is that we really can optimally solve many instances of the TSP, and certainly the ones used for planning road trips. We do not always have to settle for a solution that is “good enough.” It’s true that there are more feasible solutions to many problems than there are stars in the galaxy, but we don’t solve the problems by brute force. We more intelligently solve the problems using optimization algorithms such as the simplex algorithm (a linear programming algorithm) and cutting planes (an integer programming method). Optimization algorithms traverse through the search space and find the single optimal solution among trillions of possibilities sometimes in mere seconds or minutes. It’s truly astonishing and a great contribution to basic science.

If you want more, Bill Cook is the world’s expert on the TSP and he has many examples of optimal solutions on his web site, including a TSP rout of 24,978 cities. Read Bill Cook’s (@wjcook) book and blog about the TSP for more details about the TSP’s history, algorithms, and people.

Related posts:


the NFL football draft and the knapsack problem

In this week’s Advanced Football Analytics podcast, Brian Burke talked about the knapsack problem and the NFL draft [Link]. I enjoyed it. Brian has a blog post explaining the concept of the knapsack problem as it relates to the NFL draft here here. The idea is that the draft is a capital budgeting problem for each team, where the team’s salary cap space is the knapsack budget, the potential players are the items, the players’ salaries against the cap are the item weights, and the players’ values (hard to estimate!) are the item rewards. Additional constraints are needed to ensure that all the positions are covered, otherwise the optimal solution returned might be a team with only quarterbacks and running backs. Brian talks a bit about analytics and estimating value. I’ll let you listen to the podcast to get to all the details.

During the podcast, Brian gave OR a shout out and added a side note about how knapsack problems are useful for a bunch of real applications and can be very difficult to solve in the real world (thanks!). I appreciated this aside, since sometimes cute applications of OR on small problem instances give the impression that our tools are trivial and silly. The reality is that optimization algorithms are incredibly powerful and have allowed us to solve incredibly difficult optimization problems.

Optimization has gotten sub-optimal coverage in the press lately. My Wisconsin colleagues Michael Ferris and Stephen Wright wrote a defense of optimization in response to an obnoxious anti-optimization article in the New York Times Magazine (“A sucker is optimized every minute.” Really?). Bill CookNathan Brixius, and JF Puget wrote nice blog posts in response to coverage of a TSP road trip application that failed to touch on the bigger picture (TSP is useful for routing and gene sequencing, not just planning imaginary road trips!!). I didn’t write my own defense of optimization since Bill, Nathan, and JF did such a good job, but needless to say, I am with them (and with optimization) all the way. It’s frustrating when our field misses opportunities to market what we do.

If you enjoy podcasts, football, and analytics, I recommend the Advanced Football Analytics podcast that featured Virgil Carter, who published his groundbreaking football analytics research in Operations Research [Link].

Related posts:

 


happiness is assuming the world is linear

Linear programming is a fundamental course in every operations research curriculum. The implication of including a course on linear models at the core of our discipline is that linearity is realistic for many applications. Bill Cook addresses this big assumption  in his book In Pursuit of the Traveling Salesman, which features an important moment in operations research history at the University of Wisconsin-Madison.

News of the general linear-programming model, and the simplex algorithm for its solution, was delivered by George Dantzig in 1948 at a meeting held at the University of Wisconsin. The event was a defining moment for Dantzig, who has described often its proceedings. Like many good stories, repeated telling may have shifted a few details over the years, but all versions capture the spirit of a nervous rising star facing a large and distinguished group of mathematicians and economists. During the discussion following Dantzig’s lecture, Harold Hotelling, great in both academic stature and physical size, rose from his seat, stated simply, “But we all know the world is nonlinear,” and sat down. Dantzig was lost for a reply to such a sweeping criticism.

Suddenly another hand in the audience was raised. It was John von Neumann. “Mr. Chairman, Mr. Chairman,” he said, “if the speaker does not mind, I would like to reply for him.” Naturally I agreed. von Neumann said: “The speaker titled his talk ‘linear programming’ and carefully stated his axioms. If you have an application that satisfies the axioms, well use it. If it does not, then don’t.”

Fortunately for the world, many of its complexities can in fact be described in sufficient detail by linear models. The episode with Dantzig, Hotelling, and John von Neumann is summed up nicely by a cartoon Dantzig’s colleagues reported as hanging outside his office. It featured the Peanuts character Linus in his traditional pose, sucking his thumb and holding a blanket. The caption read, “Happiness is assuming the world is linear.”

linus_linear

HT to Jeff Linderoth for reminding me to blog about this.

Related reading:


Bill Cook’s TSP talk at the University of Wisconsin-Madison

On Monday, Professor Bill Cook, Professor in Combinatorics and Optimization at the University of Waterloo gave the Hilldale Lecture at the University of Wisconsin. See my earlier blog post about this here.

Bill’s talk on the Traveling Salesman Problem (“One NP-hard problem to rule them all“) was terrific! Bill is a master multi-tasker as evidence by how he effortlessly controlled his talk on three separate screens by three iPhones that he carried around his talk (one was strapped to his wrist).

Bill gave a great overview talk about the TSP. He talked about the history of the TSP and the main contributions, the intuition problem behind proving tours are optimal using linear programming duality and why cutting planes are helpful, and why heuristics work so well, and challenges for parallelizing the algorithms. I highly encourage reading Bill Cook’s book In Pursuit of the Traveling Salesman to learn more.

Fun TSP fact: One of the early mentions of the TSP was made by a report by Julia Robinson of the RAND Corporation in 1949, who published On the Hamiltonian game (a traveling salesman problem) [Link].

Another fun TSP fact: More recently, a woman started a 50 first dates quest via Kickstarter, where she would have a date in each of the lower 48 states plus DC and Canada [Link]. She will tour the cities and make a documentary about it. (Side note: She will probably talk about her dates more than about math in the documentary – I bet she won’t even mention cutting planes once!)

In 2012 Bill ran a TSP challenge that boasted a winning prize of $500 for finding the best tour in a 115,475-city challenge through (nearly) all cities, towns, and villages in the contiguous 48 states. [Link]. The three best tours all independently found different tours of the same length. A good approach for finding a near-optimal tour in a big TSP instance is to use a combination of local search and genetic algorithms. Local search tweaks part of a tour to make it slightly better. Genetic algorithms mix different tours to take good partial tours from two potential solutions to (potentially) find a better tour that combines their best parts. The combination is powerful. Bill has a few new TSP challenges and it sounds like he’ll buy you a beer if you solve them. Another fun fact: If you want a bigger prize, The Clay Institute offers a $1 million prize for finding a polynomial time algorithm for solving TSP.

Bill mentioned that fast computers helped to solve hard TSP instances but not for the reason that you might think. The fast computers and processors we have now are more accessible than the supercomputers that were used in early TSP research. Now we can tinker with computer algorithms on a laptop (or phone), and this helps to reduce the feedback loop in research, and the faster feedback is helpful for driving good research (more so than the fast computing itself).  I am young enough that I was surprised by one  of Bill’s comments about a 1987 TSP algorithm that took 23 hours on a supercomputer, “We were all surprised they were allowed to use that much computing time.” Time has certainly changed.

Bill ended the talk by hinting at future research directions including time travel and parallelization. Recently, there have been some publications that suggest that monkeys [Link] and bees [Link] solve TSP instances. But Bill was skeptical that monkeys will assist us with the next TSP algorithm breakthrough.

 

A tour from Newsweek published on July 26, 1954


the traveling salesman problem challenge for cheeseheads

bucky_tsp

Bucky the Badger is ready to tour Wisconsin!

This TSP blog post is in honor of Bill Cook’s lecture at the University of Wisconsin on Monday, April 7:

HF Deluca Forum

The Discovery Building.

12 – 1 pm.

More info: go.wisc.edu/salesman.

We are very excited to host Bill on Monday. Bill informally launched an information Dairyland TSP challenge on twitter, a tour through all 165 stops in America’s Dairyland [link to pdf]. What is the shortest tour? Hint: try using Bill’s TSP iPhone/iPad app!

For more reading:

Here are a few other TSP links.

xkcd on the TSP

A TSP genetic algorithm that finds a tour of the lower 48 state capitals. Courtesy of MathGifs

This video shows a visualization of Greedy, Local Search, and Simulated Annealing strategies for solving the Traveling Salesman problem.


your ideal summer beach read: In Pursuit of the Traveling Salesman Problem

If you haven’t read Bill Cook’s In Pursuit of the Traveling Salesman, I highly recommend it as the perfect summer beach read. I am way overdue for a review of this book, so this post is for those of you who haven’t read this book yet. I recommend Mike Trick’s reviews of this book on his blog and on Amazon. Instead of rehashing all the reasons why you should read the book, I will offer my reasons for why it is a fun summer beach read.

Bill’s writing style is engaging and fun. The book doesn’t overstay its welcome. Bill gets into enough detail about each topic so that the reader can appreciate the contribution or historical tidbit while not feeling like a chore (my first two requirements for summer vacation reading, which are rarely achieved by non-fiction books about science and technology).  The historical aspects of actual traveling salesman was fascinating. I enjoyed the part about Abraham Lincoln’s tour through central Illinois when he worked the Eighth Judicial Circuit as a lawyer (you’ll have to read the book to find out if this tour was optimal).

I found the chapter on TSP approximation algorithms and heuristics to be downright exciting. Every algorithm dominated for awhile until better algorithms emerged. I was familiar with some of the algorithms but not the entire tapestry of TSP algorithms, so I eagerly turned the pages until I reached the state of the art. The chapters on linear and integer programming might be a little tough for the average reader (meaning no OR/optimization/CS/math background), but the remaining chapters are accessible to a audience of general science readers.

There are a lot of great pictures in the book, and I believe the pictures are a big reason why it is so enjoyable to read. I suspect that many potential readers enjoy looking at maps, and there is no shortage of maps with TSP tours here. Often, I could look at a tour and see if the tour was “good” or not, and I could visualize how heuristics worked. I applaud Bill’s effort in putting together such great illustrations. This is an advantage for the TSP, since other optimization problems may not be able to draw from such a rich set of visuals as the TSP can.  In addition to the TSP maps, there are pictures of historic documents from actual traveling salesmen, TSP researchers (I liked the 1970s era pictures), and Robert Bosch’s beautiful TSP art. You would not want an audiobook of this book (and indeed, none is available).

In Pursuit of the Traveling Salesman is a labor of love about an important optimization problem. I feel indebted to Bill Cook for writing a book that makes optimization seem so thrilling to non-optimizers (I’m not sure I succeed at that very often on this blog). I highly recommend this book.

PS. Bill, thanks for the shout out (reference 32 in Chapter 5).

TSP at the beach

TSP at the beach


how to visit all 30 MLB baseball stadiums in a record amount of time

The Wall Street Journal reports how to find the shortest path to visit all 30 Major League Baseball stadiums in 35 days.  Of course, this is a constrained Traveling Salesman Problem (TSP) with additional constraints that take the scheduling of home games at each stadium into account. Unfortunately, the TSP was not mentioned by name in the article.  The distances between the stadiums reflect driving time and additional rest time (unless you’re a robot, you need rest before you drive).  The model was built and solved by Ben Blatt of the Harvard Sports Analysis Collective using “linear programming.” Last time I checked, the TSP was a discrete problem, and those of you who study the TSP will have to let me know if there are linear programming based heuristics that can be used.

Blatt has not been enjoying his optimal tour.  Efficiency may be beautiful, but it’s not always fun.

Are you using OR models to plan a vacation this summer?