Theoretical Operations Research Example

Finding the optimal solution for real, meaningful problems is beyond the capability of any computer if the decision problem is not modeled correctly, or if an optimization methodology is not devised to solve the problem efficiently. The total number of alternatives is usually too large for direct enumeration.

To illustrate this point, we would like to present a small theoretical example. Putting aside the complexities involved in a real problem (i.e., probabilistic rates of deterioration, the multi-period nature of the decision problem, the large numbers of condition states, and budget constraints), let us consider a simple problem from operations research literature called the "Assignment Problem." Suppose there are 70 people, capable of performing each of 70 jobs with varying degrees of cost. We want to assign the 70 people to the 70 jobs such that the total cost is minimized. Suppose we did not have any technique to solve the problem but had an extremely fast computer to compare all the alternatives. Let us call this "The Brute Force Method." Suppose this super-computer was capable of evaluating ten billion alternatives per second. The number of alternatives is 70 factorial (70!) which, using Stirling's approximation, n! ~ (n(n + .5) e -n )Ã¢Ë†Å¡2p, is approximately 10100. Clearly, the problem cannot be solved by this Brute Force Method. To obtain an appreciation of this number, suppose the computer had started working at the time of the 'Big Bang," which is thought to have occurred 15 billion years ago. The number of alternatives it would have computed by now would have been 15 x 109 years x 365 days x 24 hours x 60 minutes per hour x 60 seconds per minute x 1010 calculations per second on an extremely fast computer. This equals roughly 4.73 x 1027 computations. In fact, had the earth been covered by such computers, all working on the problem, the task still would not have been completed!

Alternatively, "The Simplex Method" of linear programming on a PC would find the optimal solution to this problem in a matter of minutes, and a specialized code for the Assignment Problem in even less time.

Let us consider a problem closer to the problem at hand. Suppose we had only 100 segments and the possibilities involved only two decisions: maintain or replace (again ignore the complexities associated with the actual multi-period nature of the problem, uncertainties, and budget constraints). Even this simplest of problems involves 2100 alternatives which is approximately 1030. In the example the super computer described earlier, this would need 3,170 billion years for its computations! On the other hand, the specialized algorithm developed for TUBIS would solve the above problem with multiple periods and budget constraints in a matter of minutes.

Of course, the pipe maintenance problem is far more intricate than the above examples. Economical and risk issues, uncertainty in deteriorations, current and future budgets, the interconnection between actions taken now and those needed in the future, and environmental issues each add to the complexity of the problem. These additional variables make The Brute Force Method an even more unrealistic way of deciding actions to be taken on a complex pipeline network.

It should be evident from the simple, illustrative examples above that operations research modeling is necessary to properly make decisions in a complex system with a large set of variables such as a pipeline, bridge, or road network.