Counter-intuitive results in OR

Question

When teaching introductory OR courses I have often found that presenting counter-intuitive or paradox-like results is a great eye-opener for the students. I use these examples and results as a motivation for why we need to learn OR techniques. One of the examples I have used is the Braess Paradox stating that adding a link to a congested road network can end up increasing the overall journey time. What other counter-intuitive results do we have in OR that could be used as motivating examples?

Answer 1

I like to introduce students to the need for optimization algorithms by talking about the traveling salesman problem (TSP). I introduce the problem statement, which is easy to do, then let them brainstorm ways to solve it. Usually students suggest methods that are similar to nearest neighbor, etc. Eventually, someone usually says something like:

If we're solving it on a computer, then why not just let the computer check all the possible routes and pick the best one?

I ask whether this method could work even for large instances, and usually the consensus is that we could solve instances with 100s or 1000s of nodes this way. We figure out together that there are $n!$ possible routes, and sometimes students revise their estimates downward, but not by much.

Then I say, OK, let's suppose my computer can evaluate 1 trillion routes per second. Then:

• To solve a 10-node instance takes 3.6 microseconds. (great.)
• To solve a 15-node instance takes 1.3 seconds. (not bad.)
• To solve an 18-node instance takes 1.8 hours. (hmm.)
• To solve a 20-node instance takes 28.2 days. (not great.)
• To solve a 22-node instance takes 35.6 years. (uh-oh.)
• To solve a 25-node instance takes 491,857.2 years.
• To solve a 30-node instance takes hundreds of times the age of the universe.

Then I tell them that the Concorde iPhone app can solve a 30-node instance in a fraction of a second, to optimality, and then it's an "easy sell" as to why we need optimization algorithms.

Answer 2

Some results are highlighted below.

1. There is one similar to the Braess paradox. In the paper by Spieksma and Woeginger, a paradox is proposed in which:

   • Increasing the speed of some machines in a no-wait flow-shop instance may actually worsen the optimal makespan. We construct instances for which the ratio between optimal makespan with improved speed and optimal makespan without improved speed becomes arbitrarily bad.

   • The authors of the paper call it the no-wait flow-shop paradox.

2. Another counterintuitive result is Bélády's anomaly. It is

   • the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns. This phenomenon is commonly experienced when using the first-in first-out (FIFO) page replacement algorithm. In FIFO, the page fault may or may not increase as the page frames increase, but in Optimal and stack-based algorithms like LRU, as the page frames increase the page fault decreases.

3. The transportation paradox, where transportation can be more costly when the number of demands/supplies is reduced.

---

_References

_{[1] Spieksma, F.C.R., Woeginger, G.J. (2004). The no-wait flow-shop paradox. ScienceDirect. 33:6. pp 603-608. https://doi.org/10.1016/j.orl.2004.10.007.}

_{[2] Bélády, L.A., Nelson, R.A., Shedler, G.S. (1969). An anomaly in space-time characteristics of certain programs running in a paging machine, Commun. ACM 12:349–353.}

_{[3] Charnes, A., Klingman, D. (1971). The more-for-less paradox in the distribution model, Cah. Cent. d’Etud. Rech. Oper. 13:11–22.}

Answer 3

Finding the shortest path from A to B on a network is easy enough that a high-schooler can do it with pen and paper (Dijkstra's algorithm).

Finding the longest path (without repeats) is much harder.

(I once edited a maths textbook where the authors had assumed that a longest-path algorithm would be a simple modification of Dijkstra's algorithm. Noooope.)

Answer 4

One nice similar result I have seen in the Open shop scheduling problem, where Three is easy, two is hard!

In the paper Gribkovskaia et al. (2006), they write:

"In discrete optimization the complexity of a problem often increases dramatically when a numerical parameter changes its value from 2 to 3. Fascinated with this issue, Eugene Lawler wrote: “Sad to say, but it will be many more years, if ever, before we really understand the Mystical Power of Twoness (or what Jan Karel [J.K. Lenstra] calls the Magical Power of Threeness): 2-SAT is easy, 3-SAT is hard, 2-dimensional matching is easy, 3-dimensional matching is hard."

However, they proved a rarely found opposite behavior.

It was proved by Glass et al. (2001) that for the two-machine open shop sum-batch problem to minimize the makespan, an optimal schedule is known to contain one, two or three batches on each machine. Also they proved that finding a two-batch optimal schedule is NP-hard. Hence it was conjectured that it is NP-hard for three-batch schedules as well. Surprisingly, Gribkovskaia et al. (2006) showed that three-batch optimal schedules can be found in linear time.

Refs.

Glass, Celia A., Chris N. Potts, and Vitaly A. Strusevich. "Scheduling batches with sequential job processing for two-machine flow and open shops." INFORMS Journal on Computing 13.2 (2001): 120-137.

Gribkovskaia, Irina V., et al. "Three is easy, two is hard: open shop sum-batch scheduling problem refined." Operations Research Letters 34.4 (2006): 459-464.

Answer 5

I belatedly realised that we've missed one of the most famous OR paradoxes of all:

In WW2, the Statistical Research Group at Columbia University considered the problem of how best to protect bombers from enemy fire. They observed patterns of bullet and shrapnel damage on bombers returning from missions over Europe. The obvious interpretation of these patterns was that bombers should be armoured in the areas that were hit most often, as shown by recorded damage frequency.

However, Abraham Wald's group realised this was exactly the wrong interpretation. The data was compiled from bombers that had survived damage. The lack of reports of damage to areas such as engines and cockpits didn't mean that enemy fire never struck these areas - rather, it meant that they didn't survive when hit in these areas, so bombers should be armoured in these locations.

Another story from WW2, though I can't remember enough specifics to find a cite for this one: ice on wings is a major danger to aircraft, and the Allies were considering installing de-icing gear on bombers, but eventually concluded that even though it improved the survival rate for bombing missions, it actually increased the danger to pilots.

The reason for this was that the weight of de-icing gear reduced the payload that bombers could carry, requiring more flights to deliver the same weight of bombs, and hence more risk from enemy fire and other causes, something which more than outweighed the reduction in crashes due to icing.

These examples might not be considered "hard OR" by modern standards, but both of them have some important lessons that are relevant to hard OR practitioners.

(I wasn't sure whether to edit this into my old answer, but since it's in a completely different area, maybe it makes more sense to separate it?)

Answer 6

One neat example is in the context of network design problems and is brought about by the concept of a Steiner node. In brief, a Steiner node is an auxiliary node that may or may not be included in a particular network design problem (say, a spanning tree or a survivable network design problem). Why would you ever need such a thing, since presumably adding such a node, optional by definition, would necessarily increase the solution cost, right? Wrong.

Consider a minimum spanning tree problem defined on an equilateral triangle with each side equal to 1, for simplicity. Clearly, the MST solution would pick any two edges for a total cost of 2. Now, suppose that you're also allowed to place a fourth node somewhere inside the triangle. Can you improve the solution cost? You could, if you remember your elementary geometry and place such a node precisely at the centroid (the intersection of the medians) of your triangle. You remember that the centroid is two thirds away from the vertex and one third away from the base and therefore the distance from the centroid to any vertex is $\sqrt{2}/3$. Therefore, connecting this Steiner node to each vertex creates a new MST on the original graph, with a total cost of $\sqrt{2} < 2$!

Watch:

If I remember correctly, this example comes from the wonderful book How to Solve It: Modern Heuristics by Zbigniew Michalewicz.

Later edit:

As an example, consider a telecommunication design problem, where each node in the given network has a connectivity requirement $\rho \ge 0$ associated with it. Steiner nodes have $\rho=0$, meaning that they may or may not be included in the solution. So-called local access nodes have $\rho=1$, meaning they should be reachable via (at least) a path from any other node in the network. Backbone nodes have $\rho \ge 2$, meaning that any other node in the network must reach the backbone node via (at least) two edge disjoint paths. In such a problem, typically the objective is to minimize the cost, the constraints are enforcing the connectivity requirements and the decision variables are the edges that have to be included in the solution. The existence of Steiner nodes leads to potential solutions like the graphs above and explaining to a pointy-haired boss why they work explains the paradox.

Answer 7

Consider a transportation problem with positive cost for all arcs. Now consider an augmented problem which is identical to the original, except there is an increase in supply at one origin, and an increase in demand by the same amount at one destination. The optimal cost of the augmented problem can be less than for the original. See EXERCISE 16 in the freely downloadable chapter 8 of Bradley, Hax, and Magnanti "Applied Mathematical Programming" for a numerical example.

Unlike all other answers so far to this question, the following is presented to the world for the first time ever. Inspired by the preceding example, I conceived of how a similar phenomenon could occur in nonlinear math: the numerical computation of the estimated variance of the ratio estimator in the Regenerative Method for Discrete Event Simulation (very much an O.R. thing). Specifically, running the regenerative simulation for $n$ cycles produces $n$ i.i.d. observations $(Y_i,\alpha_i) , i=1,\cdots,n$ with $\alpha_i \ge 0 \, \forall i $. The standard point estimator for $$r = \frac{E(Y_1)}{E(\alpha_1)}$$ is $$\hat{r}_n = \frac{\sum\limits_{i=1}^n Y_i}{\sum\limits_{i=1}^n \alpha_i}.$$ The standard estimator of $\sigma^2 = \Bbb E(Y_1 - r\alpha_1)^2$ is $$S_n^2 = \frac{\sum\limits_{i=1}^n (Y_i - \hat r_n\alpha_i)^2} {n-1}$$ and is used to form a confidence interval for $r$.

As we all know, if we have scalar data points $x_1,\cdots,x_n$, having mean $\bar{x}_n = \frac1n\sum\limits_{i=1}^n x_i$ then $$\sum\limits_{i=1}^{n+1} (x_i - \hat{x}_{n+1})^2 \ge \sum\limits_{i=1}^{n} (x_i - \hat{x}_{n})^2.$$ However, the analogue for the above ratio estimator is not true! It is possible that $$\sum\limits_{i=1}^{n+1} (Y_i - \hat{r}_{n+1}\alpha_i)^2 < \sum\limits_{i=1}^n (Y_i - \hat{r}_n\alpha_i)^2.$$ For example, $(Y_1, \alpha_1) = (1,1)$, $(Y_2, \alpha_2) = (26,2)$ and $(Y_3, \alpha_3) = (13,1)$ for which $S_2^2 = 128$ and $2S_3^2 = 126$.

Talk about counter intuitive. Whoa Nelly!! Ouch, this means there is no naturally numerically stable way to compote $S_n^2$ in one pass as there is for the i.i.d variance estimator using a Welford or similar algorithm.

Even though the math in this case is nonlinear, it is similar in spirit (at least it was to me when I conceived it more than 37 years ago) to the counterintuitive transportation problem. When we add a new data point, we have all the same "work" to do as before, plus some extra work, but the total cost decreases. This is because the new data point better "centers" $\hat{r}$ to decrease the cost of getting some of the existing work done, enough so to more than compensate for the additional "work".

Answer 8

In my opinion the following result is counter intuitive. At least it was for me when I started studying OR.

If you study probability theory, you typically start by manipulating discrete laws which are intuitive and easy to grasp, for example when you study the probability of getting a certain deck of cards, or a certain combination of balls from an urn. When studying such probabilities you perform summations and (almost) everything is nice and smooth.

Then, you are introduced to continuous laws, and sums become integrals. In my opinion, things become more complex and much less intuitive.

In operations research, it is the opposite. You start with continuous (linear) optimisation (typically with the simplex algorithm), and (almost) everything is nice and smooth. Then, you are introduced to discrete optimisation and its algorithms where the simplex is embedded in more general frameworks such as branching procedures. Discrete optimisation becomes harder to grasp.

From a computational point of view, continuous (linear) optimisation is easy, while discrete optimisation is hard. I find this counter intuitive ! I expected that manipulating finite and discrete elements would be easier than continuous ones (as in probability theory), where you have to deal with infinity at some point.

Answer 9

A very interesting paper entitled: Analysis of flow shop scheduling anomalies has been recently published by Panwalkar & Koulamas (2020)¹, that introduces the following anomalies:

1- Type 1 Anomaly: An increase of the processing time of a single operation in an optimal schedule causes a reduction in the optimal objective function value.

2- Type 2 Anomaly: Adding a job causes a reduction in the optimal objective function value.

3- Type 3 Anomaly: Adding a machine with positive processing time for at least one job causes a reduction in the optimal objective function value.

The authors discuss those anomalies in certain variants of the flow shop scheduling problem, and give insightful results.

_References:

_{[1] Panwalkar, S. S., and Christos Koulamas. "Analysis of flow shop scheduling anomalies." European Journal of Operational Research 280.1 (2020): 25-33.}

Answer 10

A classical one:

• Finding the shortest path that visits all edges of a graph is in $P$ (Chinese Postman Problem)
• Finding the shortest path that visits all nodes of a graph is NP-complete (Traveling Salesman Problem)

Another one from scheduling theory:

• $P | p_j = p | \sum w_j U_j$ is in $P$
• $P | p_j = p, \mathrm{pmtn} | \sum w_j U_j$ is $NP$-complete

This is counter-intuitive since usually, preemption makes problems easier, see "Preemption Can Make Parallel Machine Scheduling Problems Hard" (Brucker et Kravchenko, 1999).

Answer 11

There are smooth functions $f : \mathbb{R}^2 \to \mathbb{R}$ such that there exists a point $p \in \mathbb{R}^2$ that is not a local minimum, but when you restrict the function to any line through $p$ then $p$ is a strict local minimum.

Consider $f(x,y) = 2(x^2 + y^2 - 1)^2 - y^4$ and the point $p = (1,0)$ where we have $f(1,0) = 0$.

This point is not a local minimum: take the curve $(x(t),y(t)) = (cos(t),sin(t))$. Then $f(x(t),y(t)) = -sin(t)^4$. If we take $t=0$ we get our point $(1,0)$, but as we move away from this point along that curve, f goes negative.

On the other hand, for every straight line through $(1,0)$, the value of $f$ becomes strictly positive as we move a little away from that point:

We take an arbitrary straight line $(x(t),y(t)) = (1,0) + t(a,b)$, where the direction is determined by $a$ and $b$. Then we have $f(x(t),y(t)) = 2(2at + (at)^2 + (bt)^2)^2 - (bt)^4$. We consider two cases:

$a = 0$: now $f(x(t),y(t)) = (bt)^4$, so $f$ clearly goes positive along this line.

$a \neq 0$: now $f(x(t),y(t)) = 2(2at)^2 + O(t^3)$ for $t$ close to $0$. So $f$ also goes positive along those lines with $a \neq 0$.

So we have our function $f$ and the point $(1,0)$ such that $f$ increases as we move away from the point in a straight line, but $f$ decreases as we move away from the point along a curved line.