6.1 Introduction

This chapter recalls some of the most influential real-world operations research models in history. The organization is topical and introduces in context standard operations research modeling terminology. The presentation focuses on how each problem is stated, and how solutions are interpreted. Not all model solution methods are shown, but a path to access these methods is given. Neither calculus nor linear algebra is required.

Some acute modeling pitfalls are highlighted here. Most references provided herein are from widely available, approachable sources, such as Wikipedia, rather than from scholarly open literature or textbooks that a reader might not own or want to purchase. Illustrations are open source or original.

The goal here is showing, by example, how to build a model. Your model will not likely exactly match any of these examples, but will surely require necessary and reasonable simplifying assumptions.

Operations research is all about making things better, and this hopefully shows how this has been, and can be accomplished.

6.2 When Are Models Appropriate

A model is an abstraction that emphasizes certain aspects of reality to assess or understand the behavior of a system under study. The system may be physical, logical, mathematical, or some other representation of reality, such as an enterprise or some portion of one (Figures 6.1–6.4).

We concentrate on building mathematical models rather than physical ones, although much of our advice applies to those models as well. Some mathematical models can be solved analytically, algebraically in closed form, while most mathematical models can be solved on a computer, even if they are extremely complex. The value of a closed-form solution is that the entire domain of admissible inputs is accommodated and wholesale conclusions can be drawn; while a computer solution might be for a single instance of a problem and even after many such solutions with varied inputs, we only observe model behavior in the domain we have evaluated, and may need to make estimates of model behavior intermediate between those cases we have completely evaluated.

The system performs some function, and may be governed by a system operator. The system operator may be an executive or a managerial organization (e.g., a railroad), an automated control protocol (e.g., the Internet), an economic equilibrium or invisible hand¹ (e.g., traffic flows), by government regulation (e.g., income taxation), or follow scientific laws (e.g., Newton's laws). For simplicity, let's view a modeler as someone trying to respond to a problem posed by a system operator client who may work for senior stakeholders who ultimately make decisions.

At its core, a model describes the performance of a system in a particular state, and a set of admissible actions by the system operator that can transform that state.

We may also turn to models to learn how to interact with a system to achieve improved function or to avoid undesirable states.

We will look at several examples. The idea is to present a diversity of models that have historically proven innovative and effective in dealing with certain types of problems. It is rare that a new problem will be solved verbatim by any of these historical models, although a new problem often resembles one already studied. The idea is to learn how each model has been crafted to solve each problem. What are the key ideas and important insights? Some of these models have had profound historical influence and many are works of peculiar genius that are still used to solve important problems and influence policy.

The notation used in these examples is as consistent as possible with the literature and should be viewed in isolation, because there is some reuse of terms between models.

Models are particularly valuable when one cannot directly interact with or influence a system, or when doing so would be prohibitively expensive and/or dangerous (operations research was born during World War II).

Before we investigate models further, please consider these five essential steps prior to building a model. We refer to the system operator in this hypothetical engagement as “the client.”

6.3 Types of Models

Once we pass all prior hurdles, we embark on a new modeling project.

Models can be categorized based on what they are intended to achieve.

6.4 Models Can Also Be Characterized by Whether They Are Deterministic or Stochastic (Random)

Deterministic models, such as the EOQ model here, are based on constant estimates of state and performance, while stochastic (random) models recognize the random nature of some states. Some stochastic simulation models generate states from random distributions, while others seek analytic characterizations of random processes.

“Essentially, all models are wrong, but some are useful.”

G.E.P. Box

6.5 Counting

6.6 Probability

A probability² is an assessment of the likelihood that a binary event (future state) will take place, numerically ranging from zero (impossibility) to one (certainty).

“With caution judge of probability. Things deemed unlikely, even impossible, experience oft hath proved to be true.”

Shakespeare

6.7 Probability Perspectives and Subject Matter Experts³

There are at least three basic views of probability:

1. 6.7.1 Classical (sometimes called a priori or theoretical) probability assumes each of n possible outcomes of an event is equally likely, and assigns a probability of 1/n to each. This is how most people think about probability: This is appropriate if each outcome is equally likely, but generally not true and so the classic view is naïve.
2. 6.7.2 Empirical (sometimes called a posteriori or frequentist) probability uses the observed relative frequency of outcomes of repeated experiments or experiences to estimate the probability of each future outcome. Empirical probabilities will vary with different data, but their estimate will become more reliable as data from more experiments or experiences become available.
3. 6.7.3 Subjective (sometimes called personal) probability is the result of neither repeated experiments nor long-term empirical historical experience, yet is necessary, for instance, to assess the likelihood of future events with which we may have had no past experience at all. In such cases, we are forced to employ qualitative rather than quantitative experience. Speaking plainly, we may need some guesswork.

6.8 Subject Matter Experts⁴

Subject matter experts (SMEs), also called domain experts, are those with substantial experience and expert judgment in the area of interest for which we need probabilities.

A subject matter expert sometimes comes with formal credentials, such as a professional engineering certification, advanced scholarly degrees, licenses, permits, and a long, impressive resume.

However, subject matter experts may also be self-declared; before employing them, you are well advised to carefully evaluate their credentials. There is no such thing as a subject matter novice, or apprentice, so the evolution and advancement of a subject matter expert is a matter of some debate.

If the subjective probability may have results of significant consequence, we may employ more than one subject matter expert, use methods of elicitation that let us compare subjective probabilities, and attempt to reassure ourselves that the probabilities are consistent among experts, and for each expert individually.

Discovering conflicting opinions among SMEs can be valuable for an organization.

Model results must be accompanied by documentation of the exact manner in which any subjective probabilities have been assessed. Results should also include parametric evaluations of response to a range of subjective probabilities.

In the end, subjective probabilities are guesses.

6.9 Statistics⁵

Statistics involves analysis of data. Statistics is generally descriptive or predictive. Statistics seeks relationships, perhaps hidden, between measured samples of sets of states, called data sets. Data on states are either gathered by sampling a subset of a population or recorded exhaustively from every member of the population.

6.10 Inferential Statistics

Inferential statistics¹¹ assesses how much some state can be expected to vary, making statements in terms of probabilities of exceedance of a given threshold. Inferential statistics also uses probability to make decisions about whether or not some relationship exists between two types of state. A null hypothesis states there is no relationship. Based on probabilistic modeling, the null hypothesis may be accepted incorrectly, a Type I or false positive error, or the null hypothesis may be rejected incorrectly, a Type II or false negative error. Each type of error has its cost, and a test is designed to recognize these costs in setting the limits governing a decision. Reducing the risk of committing an error can be achieved by coarsening the decision rule, or gathering larger samples upon which to base statistics.

We have been told that in 2014 the average population weight of U.S. females over 20 years old was 76 kg (about 169 lb) [2]. We wonder, has this population significantly changed average weight since the 1975 random sample was collected?

Suppose the data in Table 6.1 have been hidden from us (more on this in a moment).

Now we open the data envelope. A sample mean of 62.07 kg is within our interval, so we fail to reject .

“But, wait, obviously the average population weight has increased. Why didn't we reject the null hypothesis? We would have rejected it with a critical probability of 95% and a decision interval of 48.25–75.89 kg.”

We create the hypothesis test significance level¹² before we see the test statistic—otherwise, the test statistic is not a statistic, but a known constant, and then we can rig our significance level to conclude whatever we please.

When you read about experimental results (especially, for some reason, in medical literature), you should be suspicious when you find statements such as “this result has 95.12% significance” (as might have been claimed with our example). This is a symptom of misuse: A likely explanation is that “this is as far as we could push our realized statistic to support our preferred hypothesis test conclusion.” If the scientific method is properly employed, a test is designed before the sample data are viewed. The potential costs of committing a Type I or Type II error are assessed, and the significance level is fixed. The decision and its potential risks of having made an error are known once the sample data are known. Otherwise, are you saying that the decision might be different if we change our prior estimates of the costs of making an error? That's an entirely different analysis. It is human nature to seek certainty, and scientists are human; there is continuing debate on the misuse of statistical methods [3].

We might also be criticized for unstated assumptions. For instance, the 1975 sample is from adult U.S. females aged 30–39, while the 2014 statistic applies to U.S. females aged 20 years and above. This may or may not be a serious problem, and should certainly be part of the documentation accompanying the statistical work.

6.11 A Stochastic Process

A stochastic process¹³ is a descriptive or predictive probability model yielding a location or time sequence representing the state of a system that is subject to random variation. We may want to examine the transient behavior¹⁴ of such a process, from some starting state to some limit of our interest, or from some signal state change, following system behavior afterward. Or, we may seek to examine the long-term equilibrium,¹⁵ or steady state,¹⁶ if such can be anticipated.

6.12 Digital Simulation¹⁷

Here is an abstract simulation model. This is akin to a computer procedure, written in primitive but unambiguous terms. This can be implemented in many computer languages.

When a simulation needs to represent a random event, such as the coin toss here, a pseudo-random number generator¹⁸ (an intrinsic function in almost all general-purpose and simulation computer languages) provides a stream of random numbers. Any statistical distribution can be generated this way.¹⁹ One handy feature of these generators is that they can be rigged to produce the same sequence of random numbers each time the simulation is run, the better to be able to exactly reproduce any experiment, or isolate some curious event, or bug, in the simulation behavior.

Simulations are attractive because they directly represent system operation and states, and are designed to directly exhibit symptoms of the problem being modeled.

Simulations, especially those employing random numbers, have the disadvantage, for instance, that one needs to decide how many replications are necessary to achieve a trustworthy estimate of long-term, or equilibrium (steady-state) system operation. How much “warm-up” time or distance is needed before a simulation can be trusted to be behaving as it would, essentially, forever? When we seek to discover some anticipated but rare state, how long must the system be simulated before we conclude whether or not this event should have been encountered? These are serious issues that have received substantial attention in the scholarly literature.

6.13 Mathematical Optimization²¹

The economic order quantity (EOQ) introduced previously constitutes the solution of a model, rather than the model. Now let's actually state the optimization model leading to this policy, and solve it analytically in closed form.

This Economic Order Quantity model yields a stationary solution, is stated in terms of a continuous variable, and exhibits a convex objective function; so we are confident that our solution is valid and in this case unique.

Not all optimization models can be satisfactorily solved with advice from continuous variables. Some decisions are go, no-go (binary), others involve small numbers that need to be whole numbers (for instance, if our demand is just for a few items per planning period within our decision horizon). For example, our Economic Order Quantity model may present some trouble if a particular numerical solution turns out to be, say, (in this single-variable model, we can discover the better whole number solution by evaluating the cost when we round down to one, and up to two—but we will see this strategy won't work in general).

6.14 Measurement Units

6.15 Critical Path Method^24,25

This is an invention from military operations research.

A project, from industrial to software development, consists of a number of separable activities, such as clearing a production site, pouring concrete foundations, or framing a new building. Completing necessary activities is required to achieve milestone events, such as completing framing so that finishing can begin. Each activity defines a partial order between adjacent events, where the activity cannot be commenced until all its preceding events have been achieved, and its succeeding events cannot be commenced until the activity has been completed. Each milestone event may have multiple predecessor activities, and cannot be achieved until the last of these has been completed.

Figure 6.5 shows a simple directed graph representing a project consisting of 13 activities (directed arcs) and 9 milestones (nodes). Each activity has an adjacent predecessor and successor milestone, and time duration required for its completion. The project starts at milestone s. No activity can commence until its predecessor milestone has been achieved, and that only happens when all its predecessors are achieved. Thus, we are led to follow the directed paths (alternating directed arcs and their adjacent nodes) from s through this network, determining the longest path from s to each node, and ultimately to t. An s–t path with the longest additive duration is called a critical path.

This problem, which is a bit tedious to solve manually, can be solved by some relatively simple and very fast network algorithms. It is included with optimization examples because, like with a number of simple network problems (e.g., finding connected components, cycle detection, degree assessment, shortest path, assignment, transportation, transshipment, and maximum flow) when you add realistic complications, such as consumption rates for each activity for a number of key resources, and constraints on the amount of each resource available over time, you quickly complicate the network structure with these embellishments, and need to employ numerical methods designed for these more complicated problems.

Project schedules are traditionally displayed with Gantt Charts.²⁶

6.16 Portfolio Optimization Case Study Solved By a Variety of Methods

Suppose we want to choose items from a number of item types, each with a per-item value, weight, and area. See Table 6.2.

Unfortunately, our weight and area capacities are finite, but we still want to choose a set of items with maximum value that will fit.

6.17 Game Theory³⁵

Game theory prescribes actions for opponents in conflict. In the simplest two-person, zero sum³⁶ case, each of the two opponents chooses an action in secret, and when these actions are taken, their joint consequence is some payoff from one player to the other. The following example from World War II illustrates.

In late February 1943, US-allied intelligence learned Japan would convoy troops from Rabaul, New Britain, to Lae, New Guinea, a 3-day passage (see Figure 6.6). But, allies did not know whether Japan would choose a northern route where poor visibility was forecast, or the southern route with clear weather. Allies had limited reconnaissance aircraft and fuel, and could only search either north, or south, but not both. Allied planners considered both Japanese courses of action, and both allied ones, estimating the time to detect and remaining time to attack a detected convoy (see Table 6.3). We can assume the Japanese planners did the same analysis, and came to essentially the same conclusions.

Military planning considers the enemy's most damaging course of action. If each opponent here minimizes the worst outcome, the Japanese would sail north in poor visibility, facing at worst 2 days of attacks, rather than the possible 3 days if they sailed south. This is called a minimax strategy. The allies would search north expecting no worse than 2 days of attacks, rather than as little as 1 day if they searched south. This is called a maximin strategy. Because the minimax and maximin strategies identify a single, dominant action for each opponent, there is a saddle point in this game. And that is what happened.

The Japanese were located during their northern passage, and the Battle of the Bismark Sea,³⁷ March 2–4, 1943, resulted in 13 allied casualties, and about 3000 Japanese lost.

The value of this game is 2 days of allied attacks.

Now, suppose Japan had advanced intelligence that the allies would search south. They would convoy north. The value of this intelligence to Japan is 2 − 1 = 1 attack day avoided. This is a symmetric measure of the value of intelligence to Japan, and the value of secrecy to the allies.

When one player must play first, and reveal his strategy before the other, this is known as Stackelberg Game.³⁸ The first player is called the leader, and the second the follower. These have become newly fashionable with defender–attacker models of infrastructure defense [4]. The leader (the defender) moves first with measures to defend, harden, add redundancy, or otherwise invest to make some infrastructure (e.g., the electric grid, highways and bridges, and petroleum distribution) harder to damage. The follower (the attacker) observes these defensive preparations before deciding whether, where, and how to attempt to inflict maximum damage. Two-sided optimization models of this situation simultaneously minimize the defender's damage while at once maximizing the attacker's effects. The best worst-case solution is advised.

“Mother Nature rolls dice, terrorists do not.”

E. Kaplan

Now let's hypothesize a different weather forecast, resulting in a slightly modified payoff matrix shown in Table 6.4. Now there is no saddle point. Analysis here leads to discovering a mixed strategy, where each opponent will choose an action based on a probability.

This game has an expected value of 2.6 allied attack days. There are a number of ways to arrive at this mixed strategy solution, with perhaps the easiest via optimization. We can state a simple linear program as follows:

The optimal actions for Japan can be found with a symmetric optimization (or recovered from the dual solution³⁹ of this linear program, a topic not pursued here).

Before we leave the game in Table 6.4, let's again wonder how Japan could have analyzed their prospects before deciding to convoy at all, but in anticipation of receiving intelligence before deciding to deploy. Their mixed strategy solution for the allies would have predicted a northern search with probability 0.2, and they would plan to convoy south in that case. With probability 0.8, allies could be anticipated to optimally search south, and Japan would convoy north. This expected loss of attacked days is better than 2.6 expected attacked days with no intelligence, but still might have weighed on the desperation of Japan to mount the convoy at all.

Conditioned analysis like this leads to the next class of models.

6.18 Decision Theory

Decision theory⁴⁰ offers two sorts of insight:

1. It can advise how to make optimal decisions based on probabilities of achieving particular gains or losses as a consequence.
2. It can explain why human decision makers choose other than such optimal decisions.

The amounts of potential gains or losses are typically weighed by some estimate of the probability they will occur, their expected value. Individuals have differing views of the utility, or value, of a gain or loss, and differing views of the risk, or probability that a decision will prove to be an incorrect one.

Home insurance has an expected payoff far less than the cost of the premium. Evidently, those buying home insurance are willing to pay more than its expected nominal monetary value because they have an even higher utility for such a loss than this nominal value. A lottery ticket has an expected payoff much less than its purchase price, but the utility of a large, if unlikely, payoff evidently overwhelms its comparably trivial cost.

Psychological study of decisions attempts to explain seemingly irrational choices by decision-makers. Preferences between paired alternatives may not be transitive, for instance, a shopper may prefer vehicle A over vehicle B, B over C, and C over A.

Decision theory typically applies to an individual decision-maker, unlike game theory that applies to decisions of opponents. Decision theory admits not just human choices, but those of Mother Nature too.

Mathematical models for sequences of decisions, some choices by the decision-maker, and some purely random events chosen by Mother Nature are often expressed as decision trees. The root node of such a tree is viewed as the beginning of the decisions, and weighed with a total initial probability of 1. Nodes in a decision tree are conventionally either rectangles, for decision nodes, or ovals, for random chance nodes. From each decision node, a branching set of successor arcs represents alternatives that may be chosen. From each chance node, a branching set of successor arcs represents random outcomes with the probability for each, and those probabilities summing to 1. Each arc may have a gain or loss associated with its traversal. Importantly, each probability may be conditioned on the entire preceding history of events and decisions. The ultimate states at the culmination of all decisions are represented by leaf nodes that have no successor.

Any directed path from root to leaf is a possible outcome of successive decisions and random events, and each leaf node is a possible ultimate outcome state.

The idea is to evaluate the expected value of every leaf node. This is done by backward induction, starting with the leaf nodes and backtracking toward the root, computing and accumulating expected values for successor arcs of each node.

If one maintains the decision tree as a sequence of decisions is made, and events are experienced, the tree is conditioned to have as its new root node the latest node in this set of experiences, with total conditional probability 1. All its leaf nodes have expected values conditioned by this influence.

Figure 6.7 shows a decision tree faced by a competing figure skater who must decide whether or not to attempt a very difficult “quadruple jump” during competition.

What if the probability of success is conditioned on prior experience? For example, suppose the probability of success of the first quad attempt is 0.5, and given a first success the second quad attempt will also succeed with probability 0.6, or given a first failure, the second quad will succeed with probability 0.4 (see Figure 6.8). In this case, the skater should attempt the first quad (with expected value 0.687) and attempt second quad even if the first has already succeeded (with conditioned expected value 0.854), and not attempt a second quad if the first one failed (with conditioned expected value 0.30), but attempt a quad if there was no first attempt (with conditioned expected value 0.575).

A key disadvantage of decision trees is that the number of leaf nodes (or, equivalently, directed paths or alternate outcome states) grows exponentially with the degree of the nodes (the number of successor arcs from each) and the number of successive nodes in each directed path. One signal example [5] exhibits no less than 10,032,906,240 leaf nodes, each with directed-path-conditioned probabilities.

6.19 Susceptible, Exposed, Infected, Recovered (SEIR) Epidemiology^41,42

Recent experience with the Ebola,⁴³ Zika,⁴⁴ and other infectious diseases sharpens our interest in modeling the establishment and spread of infectious diseases. Mathematical epidemiology has produced many models, among which SEIR is a good example. This is a compartmental model that divides a population into four states: susceptible, exposed, infectious, and recovered (or in the vernacular of this domain, “removed”).

Movement of individuals between adjacent states is governed by transition probabilities.

For some starting state population recovery is , if the disease abates, while a long term, steady state is called an endemic equilibrium.

Models such as SEIR are used to evaluate quarantine policies and vaccination regimes.

6.20 Search Theory⁴⁵

Search theory was the invention of mathematicians and physicists during World War II. Today, it is not widely taught outside military circles, but remains useful for finding lost things, whether they are submarines, tethered undersea mines, or you lost at sea.

One of the simplest, most elegant results is the following, known as Koopman's area search equation:

This is a conservative estimate of the probability of search success, and we can do much better if we can afford to conduct an exhaustive search. Nonetheless, this is a useful descriptive model. One corollary insight is that the instantaneous probability of success stays the same over time (that memoryless property, again), so even if you haven't succeeded so far, the expected time until success is the same. You can view this in two ways. After some time without success, a pessimist wonders: “Why have I wasted so much effort?” While hope blooms eternal for an optimist. If you are lost, hope for optimistic searchers.

6.21 Lanchester Models of Warfare⁴⁶

This is another military model developed by the British engineer F. W. Lanchester in 1914, and published 2 years later, to describe combat exchanges between opposing air forces. It has been more widely used to describe continued land combat between armies.

This is for what is called “aimed fire”: inflicted attrition is a function of the number of shooters and their accuracy, it is assumed every shooter has a target. This applies, for instance, to opposing infantry forces.

There is a parallel set of results for unaimed, “area fire” leading to Lanchester's linear law. In this case, every shooter has targets spread uniformly over a target area, so attrition is the product of the lethality of each shot, the number of shooters, and the number of dispersed targets. This applies to artillery fire.

These are descriptive models, but you can deduce it is good to have either a superior initial force or one with more lethal aiming soldiers and/or area-firing artillery.

These are also models of transient behavior rather than steady state. Annihilation of either opponent terminates combat.

You may wonder what use this has for other than military planners. There are many applications among competitors, biologic predator–prey models, and other systems whose operation involves continuous exchange rates of some sort, where the exchanges harm mutual competitors.

These closed-form, analytic solutions are derived by solving ordinary differential equations. Make modifications to the model, such as adding more constraints, and you may or may not be able to solve the result analytically. However, you can always evaluate the exchanges with simulation.

This deterministic, discrete time-increment simulation will approximate the Lanchester exchanges. To be more accurate, we can increase model fidelity by decreasing the time increment with the exchange rates and reduced proportionately to apply to these shorter epochs of combat. While a simulation like this can lend insight, quite a few replications with varied inputs would be required before you begin to suspect whether or not something like the square law still holds.

To simulate Lanchester's linear law, replace the attrition terms and by and , respectively.

6.22 Hughes' Salvo Model of Combat⁴⁷

The classic Lanchester models are aimed [sic] at large-scale sustained combat involving large numbers of combatants, many shots fired by each, and continuous warfare. In fact, thousands of shots may be required to achieve a single kill.

In contrast, we anticipate modern naval missile exchanges to involve a single, signal engagement between a small number of adversaries, perhaps capital ships, with a small number of attacking missiles that are extremely accurate, highly lethal, and perhaps vulnerable to defensive missiles trying to nullify each attack [6]. This leads us to explicitly represent the lethality of each attacking shot, the effectiveness of each defending shot, and the number of “leakers” (attacking missiles not nullified) required to kill a discrete combatant unit.

These results are expressed as discrete difference equations, rather than differential equations, and can be solved with elementary algebra.

After a missile exchange, we can make a number of assessments analogous to the continuous Lanchester ones.

A charm of the Hughes Salvo equations is they admit embellishments such as scouting to locate targets and improve aim, decoys, evasion, distraction, surprise, and so on. The resulting difference equations are still trivial to solve numerically.

6.23 Single-Use Models

Single-use models can respond to an exigent question quickly and effectively, and don't necessarily need to employ advanced mathematics.

"Compound interest is the eighth wonder of the world.

He who understands it, earns it…he who doesn't…pays it.”

A. Einstein

The following algebraic model has been used to illustrate to navy fleet commanders the impact of their policy for naval combatants to always maintain a certain level of fuel as safety stock against running out in case of unanticipated demand. Maintaining a safety stock, expressed as a percentage of fuel capacity, is a wise policy, but making minor adjustments to this percentage responding to changes in your estimate of threat level—the likelihood you will need to use a lot of unanticipated fuel right away—can have significant influence on the policy cost, born by the supply ships that must sortie to supply fuel to the combatant customers at sea.

6.24 The Principle of Optimality and Dynamic Programming

This terse statement by Richard Bellman has stood the challenge of time, and to this day nobody has found a way to expand, contract, or clarify this seminal version. What a compliment to this genius.

Rather than restating this, let's try to understand it, and exploit its implications.

Returning to our portfolio example, let's view solving this from Bellman's perspective. Let's start by choosing some number of A items, given we might have any amount of remaining weight and area capacity to fill. We would greedily and correctly (in fact, optimally) pack as many A's as we could fit. If we create a schedule of the number of A's that will fit in any particular remaining weight and area capacity, we could record this is a matrix for remaining weight , and remaining area .

Now, suppose we choose some number of B items, also for any remaining weight and area capacity. Now an optimal choice would account for the immediate value of the B items chosen, plus the value of A items for which we leave unused weight and area capacity. So, for example, if we have remaining (weight, area) capacity (21,40) and chose one B item with value 79, this would leave capacity (21−8 = 13, 40−16 = 24), and by lookup in the A item table, we could see that we still have capacity to choose one A item with value 120. We can continue similarly with C and then D items.

This works because the weight and area requirements for items are whole numbers, so there are a finite number of (weight, area) capacities in the state space of this problem. We refer to each sequential item-by-item enumeration of what will immediately fit in any available remaining capacity the stage of selection.

Expressing this more compactly, represent item types by index and the remaining weight capacity and area . Let be the value of items selected through stage i.

Verbally, this tells us that for given available capacity at stage i, we choose that maximizes the immediate item i value in addition to the optimal prior selections, if any, through stage i−1 of the capacity, our choice of would leave . In more detail, we would carefully control the maximization at each stage:

That is, we only search over whole numbers of items that can fit in remaining capacity (w,a).

We read out the final, optimal solution by tracing back through our stage matrices. gives us the optimal portfolio value. This portfolio includes items of type I. gives us the number of items i−1, and so forth.

For our numeric example and stage sequence we get

The optimal solution leaves five area units unused, which is revealed by .

This systematic enumeration is called dynamic programming [7],⁴⁸ and although it works just fine for our example, the total number of evaluations inside the maximization for all item stages and all states is 467,814, so we would have been better off enumerating by brute force the 41,769 item permutations. This is evidence of what is called the curse of dimensionality.⁴⁹ However, for many problems, dynamic programming offers dramatic improvements in enumeration.

6.25 Stack-Based Enumeration

Directed graphs and networks (graphs with data attributes) frequently arise in modeling, and we end up seeking ways to maneuver through these with some goal in mind.

In order to enumerate all directed paths (alternating sequences of nodes and arcs) from a given source s to a given sink t in a directed graph G = (N,A), we must use an algorithm and data structures that ensure (1) completeness of the enumeration (we don't miss any paths) and (2) uniqueness (we don't want to report any path twice).

The basic concept behind path enumeration is the construction of a partial s–t path, and the enumeration of all possible completions of that path. A partial s–t path is a directed path between s and some other node, k (see Figure 6.9). The set of all completions of this partial path is the set of all k–t paths that do not use any nodes already in the partial path from s to k.

This is just a recursive description, and it seems circular, but note that the k–t path enumeration subproblem is solved on a smaller network than G. In fact, when the current partial path includes every node but t, there is at most one single completion of the current path: jump directly to t, if there's an arc.

To fully define an algorithm, then, we need a way of defining unambiguously a current partial path, and we need to know how to build all completions of the current partial path (avoiding nodes already on the path). This is accomplished with a mechanism to extend a current partial path by adding one arc.

The best way to understand a procedure like this is to define an instance precisely.

6.25.3 Generating Permutations and Combinations

Many problems arise involving sequences, such as the order in which successive operations are carried out, cities are visited, and tests are conducted. How do you generate all permutations⁵³ of a set of objects? Suppose we have a set of n objects and we are interested in looking at all permuted sequences of k of these at a time. The number of such permutations can be denoted

One of the most straightforward ways to generate permutation sequences on a computer is, surprisingly, by designing a directed graph with the n objects used as node labels and the subset size k as the number of echelons (Figure 6.10).

For the directed graph in Figure 6.10, there is a path for every subset of labels (a,b,c), lexicographically ranging from s,a1,a2,a3,t to s,c1,c2,c3,t.

To restrict our program to produce permutations of the labels a, b, and c, we arrange the test OK_to_add(j) in our stack-based enumeration procedure to be false if a label j already appears in the stack. This is as simple as associating with each node j a single bit representing stack occupancy.

If we want permutations of all subsets of size k, we just eliminate graph echelons beyond the kth one, and run the same procedure. We can also condition the permutations and filter out undesirable ones by either editing the directed graph to eliminate unwanted adjacencies in any permutation, or adjusting the test OK_to_add(j) to sense any undesirable permutation as soon as the top-1 contents of the stack appear so. This admits adding numerical attributes to the nodes and/or adjacency arcs, creating from our graph a network, and computing fitness of partial orders in the logic of OK_to_add(j).

We can also alter the directed graph to produce other results with path enumeration. For instance, the directed paths in Figure 6.11 select all combinations⁵⁴ (unordered) subsets of the labels a, b and c, in alphabetic order. If we again employ our handy filter OK_to_add(j) to be false when top equals k−1, we will enumerate all combinations of k out of n.

6.26 Traveling Salesman Problem: Another Case Study in Alternate Solution Methods

The traveling salesman problem⁵⁵ has been known since antiquity by, well, traveling salesmen. How do you start from your home city and visit n−1 other cities exactly once and return home while having traveled the minimum possible distance? Such a tour is called Hamiltonian⁵⁶ (after a nineteenth century Irish mathematician who first stated it carefully), or traceable path (because you can connect dots on a map on such a tour without touching a dot twice or lifting your stylus before returning to your home city).

Table 6.5 shows a 10-city example that is symmetric and fully dense.

Getting an admissible solution to this problem is as easy as selecting n cells in this table, one per row (even though these distances are symmetric, let's say a row is an origin), and one per column (destination). Although any such selection would work, the one with minimum total travel time has length 5726 km. This selection is shown in Table 6.6.

This relaxed solution consists of subtours, each separated in the table. The value of this relaxation provides a lower bound on the value of an as-yet unknown optimal solution.

Now just visit these cities in alphabetic order, which in this full-dense problem will surely be admissible as a tour (see Table 6.7).

This is a Hamiltonian tour with total distance 13,125 km. This is an admissible solution with no subtour, so its value provides an upper bound on an as-yet unknown optimal solution.

There are possible tours in this full-dense problem.

Why not enumerate with our directed graph enumeration procedure? We could do so here. But with a full-dense problem with 60 cities, there are on the order of admissible solutions. This is more than the cosmologists' estimate of the number of atoms in the universe.

There is a huge literature on how to get better solutions faster for this problem, and more realistic ones with side constraints on, for instance, time windows when we can visit each city.

Nevertheless, even simple heuristics and some elementary computer procedures can have beneficial effect. For instance, here we start with the alphabetic tour of our full-dense problem and select a random city in this tour. We evaluate moving it from its present position in the tour to some other random one. If this decreases our total tour length, we make the change. Otherwise, we randomly try again. Figure 6.12 shows the progress of our Monte Carlo simulation.⁵⁷

In this relatively simple instance, an optimal solution with length 7,486 km is shown in Table 6.8.

Now, let's move to a just slightly larger problem, with all of the 24 European cities in our reference database. Now we have 23! solutions or somewhat less than of these. (The 23 coincidence is just that.) A minimal length selection with each city an origin once and a destination once has length 10,194 km (a lower bound on the solution we seek, an alphabetic tour has length 33,117 km (an upper bound), and an optimal tour has length 12,288 km (see Table 6.9).

Starting with the alphabetic tour, our Monte Carlo method eventually discovers a tour with length 12,965 km at random-exchange trial 1545, and discovers no further improvement over an additional ten million random-exchange trials (see Figure 6.13).

6.27 Model Documentation, Management, and Performance

A carefully crafted model formulation can help assess model performance as the model is scaled up to include either more elements, or more detail on each element.

6.28 Rules for Data Use

“What gets measured, gets managed.”

P. Drucker

The number and diversity of sources of data necessary to support a real-world model is surprising. A simple model of shipment planning can quickly call for road networks, freight rates from commercial sources, postal rates, state regulations, labor agreements, carrier policies, system operator policies, restrictions on mixed commodities, operating costs, and so on. Not only does a model need a lot of data from many sources, it will depend on the currency and accuracy of this data over all its life.

The following is a representative sample of common types of data sources, and the rules that govern data from each.

6.29 Data Interpolation and Extrapolation

Data interpolation and extrapolation⁷⁵ are predictions used to fill in gaps, especially in temporal or spatial data series where we have some observations of a dependent state value for some, but not enough associated values of independent states (see Figure 6.14). As the names imply, interpolation applies inside the range of observed independent state values, and extrapolation elsewhere.

A modeler needs to assure there are no reasons to suspect systematic misbehavior of the prediction function within independent state values, and especially outside them. Extrapolation requires more faith that the validity of the prediction function extends beyond the range of our observations, and for this we need as much supporting evidence as possible.

Referring back to our regression model of weight as a function of height for a group of American females aged 30–39, interpolation might be reasonable within the range of observed heights from 1.47 to 1.83 m (about 4′ 10″ to 6′). But an average newborn female has height 0.51 m (about 20″) and weighs 3.6 kg (about 7.7 lbs), and extrapolation yields 70 kg (about 154 lbs). Similarly, extrapolating to heights greater than the observed 1.83 m will soon yield results beyond those to be expected for human females.

6.30 Model Verification and Validation

“To get a large model to work you must start with a small model that works, not a large model that doesn't work,”

D. Knuth

Model verification and validation have long been a source of debate.^76,77,78

6.31 Communicate with Stakeholders

“The purpose of computing is insight, not numbers.”

R. Hamming

This is a continuous requirement from first client meeting to presentation of intermediate or final results. Model development inevitably encounters surprises. Anticipated, required data may not be available when needed, or trustworthy, or expressed in immediately useful form. The stakeholders may include not just the client, but also representatives of other interested groups (for instance consultants, domain experts, regulating agencies, and others). If the modeler has prepared well, successful presentations based on concrete model outcomes are the ideal outcome. There will likely be presentations for planners who deal with the problem and others for the executives who pay the bills. For each stakeholder, one must carefully adhere to the lexicon worked out in the five-step preparation (see prior definition of such) for the modeling project.

“Almost all senior analysts have similar stories about how they learned not to brief a senior executive.”

J. Kline

Managing relationships with multiple stakeholders, and following their multiple, possibly conflicting, objectives is beyond the scope of this introduction. But suffice to say, if you have scrupulously followed the five-step preparation above, you are as well situated as possible.

Most contemporary models are used via a graphical user interface (GUI), and in many cases the GUI consumes more development effort than the model. This is to be expected. However, the GUI developer(s) and modeler(s) are not necessarily the same individuals, and this calls for constant, careful coordination. There are wonderful models with poor GUI's, or none at all, and fantastic GUI interfaces to terrible models. Better to sort out which is which. Some of the most successful GUIs have appeared (though is has some vexing bugs traversing the International Dateline) for mobile applications on portable devices. Google Earth⁸¹ is a superb example.

Although there are a host of commercial GUI developer kits available, some particularly successful applications have been developed quickly, and on the cheap, by co-opting, for instance, the Microsoft Office suite of applications (Excel, Access, Project, etc.) These packages represent hundreds of millions of dollars of development, all aimed at the sort of system operator the modeler is likely to encounter. Despite all the criticisms of any particular software suite, such as this one in particular, it presents a huge opportunity to develop a model, supporting data base(s), and GUI, with the reasonable expectation that the planners will already be quite familiar with the tools employed.

6.31.4 Persistence and Monotonicity: Examples of Realistic Model Restrictions

Now suppose we have briefed our solution, and the client admits that the maximum weight budget was an estimate, that there may be some variation in the true maximum weight, and asks us for a parametric sensitivity analysis of possible maximum weights ranging from 95 to 105 kg. The client wants to be ready to brief for these contingencies.

The 11 rows following “optimal” in Table 6.10 show optimal selections as we vary maximum weight from 95 to 105 kg. A reasonable client will hate these optimal results. How do you explain a selection portfolio that exhibits so much chaotic turbulence as one simple parameter, maximum weight, is gradually, systematically increased? Well, declaring “this is optimal” will not likely suffice.

max weight	Sel wgt	Sel area	A	B	C	D	Total value	Base portfolio
Continuous
100	100	200	7.41	0.00	0.00	3.70	1014.8
Optimal
95	95	198	6	1	0	5	969
96	96	194	7	0	0	4	976
97	97	194	6	2	0	3	980
98	98	199	6	1	1	4	990
99	99	195	7	0	1	3	997
100	99	195	6	2	1	2	1001	base
101	101	200	7	1	0	3	1021
102	102	196	8	0	0	2	1028
103	103	196	7	2	0	1	1032
104	104	192	8	1	0	0	1039
105	105	197	8	0	1	1	1049
The Continuous row shows the relaxed solution when we do not require whole numbers of items. Anticipating a possible change to the weight budget, we parametrically evaluate Optimal whole number solutions from 95 to 105 kg. The Optimal portfolios bear little resemblance to their adjacent neighbors. This would be a difficult set of solutions to brief. (Note that rounding the Continuous relaxation to nearest whole numbers would not discover the Optimal base portfolio solution.)

Clients expect parametric transitions that are intuitive. Here, the client might prefer a base portfolio, say the one we produced with maximum weight 100 kg. Then, each time we reduce the weight budget, we only permit deletion of a single item from this base portfolio when we must, retaining the rest. Conversely, as we increase weight budget from base, we only allow a new item to be selected in addition to those already in the portfolio. This is intuitive. Less weight budget, fewer item selections, more weight budget, more item selections, while always preserving all but one item in the portfolio. This is concise. These are called monotonic parametric solutions. In Table 6.11, you will find “monotonic” results for the base portfolio with maximum weight 100 kg.

max weight	Sel wgt	Sel area	A	B	C	D	Total value	Base portfolio
Monotonic
95	94	175	6	2	1	0	933
96	94	175	6	2	1	0	933
97	97	185	6	2	1	1	967
98	97	185	6	2	1	1	967
99	97	185	6	2	1	1	967
100	99	195	6	2	1	2	1,001	base
101	99	195	6	2	1	2	1001
102	99	195	6	2	1	2	1001
103	99	195	6	2	1	2	1001
104	99	195	6	2	1	2	1001
105	99	195	6	2	1	2	1001
Persistent
95	95	189	6	1	1	3	956
96	95	189	6	1	1	3	956
97	97	194	6	2	0	3	980
98	97	194	6	2	0	3	980
99	97	194	6	2	0	3	980
100	99	195	6	2	1	2	1001	base
101	99	195	6	2	1	2	1001
102	102	200	6	3	0	2	1025
103	102	200	6	3	0	2	1025
104	102	200	6	3	0	2	1025
105	102	200	6	3	0	2	1025
The Monotonic solutions allow at most one item deletion per max weight reduction from the base portfolio, and at most one item addition for each budget increase from the base portfolio. These do not use all the weight budget, and may be too restrictive. The persistent solutions at the bottom allow at most one deletion and at most one addition. This intermediate restriction may be acceptable.

The client may be disappointed that from 100–105 kg maximum weight budget, no new monotonic item is selected. This is because the area constraint requires that we make room for a new selection by deleting some existing ones, and the client told us not to do this. The monotonic solution is a restriction of the optimal solutions that did make such substitutions (with excess gusto) and with respect to the base portfolio, this restriction reduces our maximum total value selected.

A reasonable client might then agree, “OK, you can make room for a new item selection by deleting an existing one, but never more than one of each to keep things simple to explain.” This is an example of persistent parametric solutions, here limiting the changes to at most two per adjustment of maximum weight budget. These results are shown in the “persistent” section of Table 6.11.

These persistent results are a restriction of optimal ones, but not as restricted as monotonic selections. Note the maximum total value selected is no better than optimal, and no worse than monotonic.

A reasonable client may ask for more variations like these, seeking insight, but more important seeking some way to understand results in order to persuasively convince others to change policy and follow our advice. Figure 6.15 shows portfolio values as we vary our maximum weight budget.

“A manager would rather live with a problem he cannot solve than accept a solution he cannot understand,”

G. Woolsey

6.32 Software

An analyst generally needs familiarity with and access to a number of software tools: text editor, presentation slide maker, spreadsheet, graphics, statistics, simulation, optimization, general-purpose programming, and geographic information system. If you are affiliated with an educational institution, you likely have free access to a wide variety of software packages that would normally cost a lot more than your portable workstation. This provides a great opportunity to try a variety of packages.

Even if you are not affiliated with an educational institution, there are a number of excellent, inexpensive, or free software packages. For instance, the Microsoft Office Suite⁸⁴ includes the text editor Word, the presentation slide maker Powerpoint, and spreadsheet Excel, which includes graphics features. The statistics package R⁸⁵ is free and well documented. Many simulation packages⁸⁶ are freely available, offering libraries of random statistical generators and live animations. Some optimization software⁸⁷ is available in Excel, and a large variety of other packages are available. General-purpose programming languages such as Python⁸⁸ are available and well documented. Google Earth⁸⁹ provides a globe, map, and a geographic information system; a user can mark points, draw objects, and create animations on the Earth's depicted surface, political and geographic features can be depicted as the viewer's perspective moves over, toward, or away from the surface, and these displays are portable between computers via simple email attachments. Some graphics software⁹⁰ is embedded in the preceding suggestions, but more general utilities can be used to create still images and movies.

When choosing software, make sure each package can be added to your modeling federation as a compatible component. Look for examples of, for instance, a spreadsheet that can invoke a simulation as a subroutine. If you suspect you'll need some help, check for online blogs and a users' group that supports a package. Also, be mindful that the more existing users there are, the less likely the package is to exhibit annoying bugs. It is said that Microsoft Excel has more than a billion users worldwide: that's a lot of experienced potential users for anything you create with it.

6.33 Where to Go from Here

The INFORMS journal Interfaces is aggressively edited for clarity of exposition and includes many modeling examples explained with care; refreshingly, some recounting of false starts and lessons learned also appear. The INFORMS newsletter OR/MS Today features some articles about modeling, including the shared experiences of clients and modelers, some analysis puzzles, and entertaining features about the operations research (and modeling) craft. To access more of our huge open literature of articles and textbooks, some mathematical preparation will be necessary, including at least algebra, probability, statistics, and elementary modeling. An introductory modeling course with a lot of homework drills does wonders: the best way to learn how to model is to try modeling.

“Anyone who has never made a mistake has never tried anything new.”

A. Einstein

6.34 Acknowledgments

The author is grateful for helpful comments (and suggested examples) from colleagues Dave Alderson (game theory), Matt Carlyle (enumeration), Rob Dell (palatable solutions), Jeff Kline (Hughes equations), Bob Koyak (regression), Kyle Lin (figure skating decision theory), Connor McLemore (example physical and mathematical models), and Al Washburn (EOQ); two anonymous reviewers (misuse of p-values, data analytics); and the editor (characterizing probability).

References

1. 1 Delury G (1975) The World Almanac and Book of Facts. Sacramento Bee.
2. 2 Centers for Disease Control and Prevention. (2017) Body Measurements. Available at https://www.cdc.gov/nchs/fastats/body-measurements.htm.
3. 3 Baker M (2016) Statisticians issue warning on P values. Nature 531 (7593): 151.
4. 4 Brown G, Carlyle M, Salmerón J, Wood K (2006) Defending critical infrastructure. Interfaces 36: 530–544.
5. 5 National Research Council (2008) Department of Homeland Security Bioterrorism Risk Assessment: A Call for Change. Available at https://www.nap.edu/catalog/12206.
6. 6 Hughes W (1995) A Salvo model of warships in missile combat used to evaluate their staying power. Naval Res. Logist. 42: 267–289.
7. 7 Bellman R (1954) The theory of dynamic programming. Bull. Am. Math. Soc. 60 (6): 503–516.
8. 8 Brown G, Dell R, Wood R (1997) Optimization and persistence. Interfaces 27: 15–37.
9. 9 General Services Administration. (2017) Rules and Policies – Protecting PII – Privacy Act. Available at http://www.gsa.gov/portal/content/104256.
10. 10 Department of Homeland Security. (2017) The Protected Critical Infrastructure Information Management System (PCIIMS). Available at https://www.dhs.gov/pcii-management-system-pciims.
11. 11 Office Of Naval Research. (2017) Human Subject Research Documentation Requirements. Available at https://www.onr.navy.mil/About-ONR/compliance-protections/Research-Protections/Human-Subject-Research.aspx.
12. 12 Federal Bureau of Investigation. (2017) Security Clearances for Law Enforcement. Available at https://www.fbi.gov/resources/law-enforcement.
13. 13 United States Patent and Trademark Office. (2017) Basic Facts Breakdown – Trademarks, Patents and Copyrights. Available at https://www.uspto.gov/trademarks-getting-started/trademark-basics/trademark-patent-or-copyright.
14. 14 Bradley G (1986) Optimization of capital portfolios. Proc. Natl. Commun. Forum 40 (1): 11–17.
15. 15 Geoffrion A (1986) Capital portfolio optimization: a managerial overview. Proc. Natl. Commun. Forum 40 (1): 6–10.