When you hit the “run” button to solve a network design problem, you are starting a very hard mathematical optimization problem.  However, since machines keep getting faster and the optimization algorithms keep getting faster, you often see very reasonable run-times.

But, the underlying math is still a problem.  And, as Pete Cacioppi points out, it can be jarring for a user to make a small change in the problem and see the run times dramatically increase.

As Jean Francois Puget pointed out, the complaints about the long run times mean that people see the value and just want to solve larger problems.  I pointed to the Wikipedia article that shows that these problems are hard and to a long-standing offer of $1 million to anyone who can crack this code.

Still, these explanations don’t always help.  The person running the optimization is still baffled–  the model ran previously, but now doesn’t.  They don’t see a reason.

The problem is that the definition from Wikipedia and the contest seem to imply that the run times will always be terrible.  This is not the case.  Many times, the run times are quite good.

So, Jean Francois, Pete, and I exchanged a few emails to try to come up with a better way to explain what is going on.  With these problems, you can think of every different version of the problem (some with tweaks to the data or changes to the constraints).  Many of these versions will solve fine, and yet, some will not solve at all.  And, what Wikipedia’s article suggests is that there is no way to know in advance.

We came up with two explanations:

• Solving these problems can be like navigating a mine field.  Sometimes you hit a version of the problem where the run time explodes.
• Solving these problems is like golf.  Despite doing what you think is the same thing, this time you end up in the water, in the sand trap, or 20 strokes higher than your last game.

If you have better explanations, we would like to hear them.