One of the problems that you can run into when doing a large network design project is the run times of the models.  Sometimes, the models you want to solve simply take much too long to solve or never solve at all.

Luckily, many network design problems do not encounter this problem.  And, good modeling techniques still allow you to get the answer you need to the most complex problems.

However, you will likely still need to explain to others on the project or in the organization why you can’t guarantee a fast run-time.  This question is relatively easy to answer, but our experience shows that people don’t believe the answer (we’ll share more on this in some future posts).

People don’t believe the answer because they’ve heard of cases of large models being solved quickly and they’ve models help give them answers to complex problems.

In any case, there is no guarantee that a network design model will run fast.  Roughly speaking, the field of computer science breaks these types of problems into two classes:  P and NP.  Problems in P can have guaranteed run times that scale in a linear fashion with the size of the problem.  Problems in NP do not scale linearly, but much much faster. So, a 10X increase in the size of the model may generate a 10000X increase in run time (pushing the run time into decades or more).

Network design problems fall into the class of NP problems.  If network design software vendors could guarantee run-times, they would.

As a fun fact about the difficulty of these problems, there has been a standing $1 Million prize (since May of 2000) for anyone who can show that NP problems can be solved like P.  So, if you can guarantee the run times of these problems, you can collect a $1 Million prize.