https://or.stackexchange.com/questions/506/counter-intuitive-results-in-or Stack Exchange Network Stack Exchange network consists of 178 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers. Visit Stack Exchange [ ] Loading... 1. 2. 0 3. +0 4. + Tour Start here for a quick overview of the site + Help Center Detailed answers to any questions you might have + Meta Discuss the workings and policies of this site + About Us Learn more about Stack Overflow the company + Business Learn more about hiring developers or posting ads with us 5. 6. Log in Sign up 7. current community + Operations Research help chat + Operations Research Meta your communities Sign up or log in to customize your list. more stack exchange communities company blog Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up. Sign up to join this community [ano] Anybody can ask a question [ano] Anybody can answer [an] The best answers are voted up and rise to the top Operations Research 1. Home 2. 1. Public 2. Questions 3. Tags 4. Users 5. Unanswered 3. Teams Stack Overflow for Teams - Collaborate and share knowledge with a private group. [teams-illo-free-si] Create a free Team What is Teams? 1. Teams 2. Create free Team Teams Q&A for work Connect and share knowledge within a single location that is structured and easy to search. Learn more Counter-intuitive results in OR Ask Question Asked 2 years, 7 months ago Active today Viewed 7k times 45 23 $\begingroup$ 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? teaching Share Improve this question Follow edited Jun 16 '19 at 13:01 [RpS] LarrySnyder610 12.2k11 gold badge2727 silver badges9797 bronze badges asked Jun 16 '19 at 11:32 [Q8G] SuneSune 4,04711 gold badge1111 silver badges2424 bronze badges $\endgroup$ Add a comment | 10 Answers 10 Active Oldest Votes 36 $\begingroup$ 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. Share Improve this answer Follow answered Jun 16 '19 at 13:19 [RpS] LarrySnyder610LarrySnyder610 12.2k11 gold badge2727 silver badges9797 bronze badges $\endgroup$ Add a comment | 22 $\begingroup$ 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 Belady'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] Belady, 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. ] Share Improve this answer Follow edited Jun 27 '19 at 18:36 answered Jun 16 '19 at 13:07 [4fa] TheSimpliFireTheSimpliFire 4,86344 gold badges1616 silver badges5252 bronze badges $\endgroup$ Add a comment | 19 $\begingroup$ 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.) Share Improve this answer Follow answered Jun 20 '19 at 2:12 [7ea] Geoffrey BrentGeoffrey Brent 1,67733 silver badges1313 bronze badges $\endgroup$ 4 * $\begingroup$ +1 Although whether it is counterintuitive depends on your intuition. For instance, see my answer or.stackexchange.com/questions/13/... in which for every "easy"convex optimization problem with nonlinear objective, there is a corresponding difficult concave optimization problems in which the sense (min or max) is reversed from the original problem. $\endgroup$ - Mark L. Stone Jun 20 '19 at 15:15 * $\begingroup$ @MarkL.Stone Indeed. It was counter-intuitive to the authors who wrote that textbook, at any rate! $\endgroup$ - Geoffrey Brent Jun 21 '19 at 1:07 * $\begingroup$ Well, that actually does work for directed acyclic graphs, so the authors' confusion is perhaps understandable (if those were the only examples they had seen), if not forgivable for someone claiming to be expert enough to write a textbook. $\ endgroup$ - mjsaltzman Jun 27 '19 at 15:07 * 1 $\begingroup$ @mjsaltzman no, the working examples in the book were non-directed and had cycles. In fairness to my authors, I don't believe they ever claimed expertise in this. An education board decided network theory should be on the curriculum, and the teachers who write high school maths texts had to scramble to learn it so they could put a book out. It's understandable that some things will fall through the cracks, and this is why the publisher pays somebody (me) to check their work. $\endgroup$ - Geoffrey Brent Jun 29 '19 at 23:57 Add a comment | 16 $\begingroup$ 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. Share Improve this answer Follow answered Jul 1 '19 at 3:53 [x0s] MostafaMostafa 1,97477 silver badges2626 bronze badges $\endgroup$ Add a comment | 16 $\begingroup$ 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. A diagram of a WW2 bomber showing red spots for areas where returning aircraft showed damage. Some parts of the plane have many spots, others such as the engines and cockpit have none. 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?) Share Improve this answer Follow answered Nov 11 '19 at 22:45 [7ea] Geoffrey BrentGeoffrey Brent 1,67733 silver badges1313 bronze badges $\endgroup$ Add a comment | 13 $\begingroup$ 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: enter image description here 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. Share Improve this answer Follow edited Jul 3 '19 at 15:23 answered Jun 24 '19 at 0:39 [8b5] baudolinobaudolino 69933 silver badges1010 bronze badges $\endgroup$ 4 * $\begingroup$ This example applies to geometric length in euclidean space. Can you explain a little more how this relates to network design? $\endgroup$ - fhk Jul 2 '19 at 18:03 * 1 $\begingroup$ I have added an example to my original post. Hope this helps. $\endgroup$ - baudolino Jul 3 '19 at 15:23 * $\begingroup$ Somewhat related: rockets $\endgroup$ - ktnr Aug 21 '19 at 16:18 * $\begingroup$ @baudolino not that it changes the validity of your example, but shouldn't the distance from the centroid to any vertex be $\sqrt{3}/3$ as you're looking at $2/3$ of $\sqrt{1- 1/ 4}= \sqrt{3}/2$? $\endgroup$ - EhsanK Nov 24 '19 at 19:28 Add a comment | 10 $\begingroup$ 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". Share Improve this answer Follow edited Jun 19 '19 at 0:28 answered Jun 16 '19 at 13:49 [3rX] Mark L. StoneMark L. Stone 9,99711 gold badge2222 silver badges5454 bronze badges $\endgroup$ Add a comment | 6 $\begingroup$ 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. Share Improve this answer Follow edited Nov 12 '19 at 19:27 [4fa] TheSimpliFire 4,86344 gold badges1616 silver badges5252 bronze badges answered Nov 12 '19 at 11:41 [WGG] KuifjeKuifje 8,04511 gold badge1111 silver badges3535 bronze badges $\endgroup$ 2 * 1 $\begingroup$ I would not say that continuous optimization is easy, but rather than convex continuous optimization is easy. For instance, the resolution of non-convex (continuous) QCQP problems is NP-hard. But I agree with you concerning linear optimization, introducing discrete variables complexify a lot the problems. $\ endgroup$ - fpacaud Nov 12 '19 at 12:46 * $\begingroup$ Yes I agree ! I was refering to linear (i.e., convex) optimization. Anything non linear quickly becomes ugly ^^ $\endgroup$ - Kuifje Nov 12 '19 at 12:57 Add a comment | 6 $\begingroup$ A very interesting paper entitled: Analysis of flow shop scheduling anomalies has been recently published by Panwalkar & Koulamas (2020)^ 1, 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. ] Share Improve this answer Follow edited Apr 13 '20 at 10:06 answered Apr 13 '20 at 7:03 [x0s] MostafaMostafa 1,97477 silver badges2626 bronze badges $\endgroup$ Add a comment | 0 $\begingroup$ There are smooth functions on $\mathbb{R}^2$ such that $0$ is not a local minimum, but when you restrict the function to any line through the origin then $0$ is a strict local minimum. Share Follow answered 1 min ago [71f] JulesJules 101 New contributor Jules is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct. $\endgroup$ Add a comment | Your Answer [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] Thanks for contributing an answer to Operations Research Stack Exchange! * Please be sure to answer the question. Provide details and share your research! But avoid ... * Asking for help, clarification, or responding to other answers. * Making statements based on opinion; back them up with references or personal experience. Use MathJax to format equations. MathJax reference. To learn more, see our tips on writing great answers. Draft saved Draft discarded [ ] Sign up or log in Sign up using Google Sign up using Facebook Sign up using Email and Password Submit Post as a guest Name [ ] Email Required, but never shown [ ] Post as a guest Name [ ] Email Required, but never shown [ ] Post Your Answer Discard By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy Not the answer you're looking for? Browse other questions tagged teaching or ask your own question. Featured on Meta * New post summary designs on site home pages and greatest hits now; everywhere... * We've made changes to our Terms of Service & Privacy Policy - January 2022 Linked 8 How to convince people that OR can help them? 12 Convex Maximization with Linear Constraints 9 Intuition behind more-for-less transportation paradox? Hot Network Questions * Why is FTL travel impossible if the universe expands FTL? * FIDE Rating Distribution * Estate Agents must pass on all offers made on a house - UK Legislation * What does assignment to a bracketed expression mean in C#? * What is that plane flying over Missouri at 59,700 ft? * Delta-v to hit the moon: is reaching Lunar L1 enough? * Why don't errors accumulate in climate models when the time horizon increases? * __________ is the way to go! * How can I increase the proximity damage from Ashardalon's Stride? * ls it wrong to not have any research ambitions after PhD and postdoc experience? * BBC: "A rocket launched by Elon Musk's space exploration company is on course to crash into the Moon and explode." Will it really explode? * Animate finding the middle (hypercube edition) * How would an entity automatically know when someone is directly observing it? * Is this ship resurrection spell balanced for 4th level? * Geometry Nodes: How the nearest face is found? * Identifying strange SMD audio capacitor * I factory reset my m1 macbook, it still contained my name =( * Is the rule of when to add the articles: (a, the, no article) before a noun, too flexible in English? * What does the word "numquid" literally mean? * The more I improve the quality of my course, the worse the student evaluation becomes. Should I provide low quality lectures? * What are the other ways of energy transfer apart from heat and work? * How to put Break command within a Do loop over 2 variables * What was this movie I saw billed as the "Worst SF movie ever"? * Running GUI apps under WSL more hot questions Question feed Subscribe to RSS Question feed To subscribe to this RSS feed, copy and paste this URL into your RSS reader. [https://or.stackexch] * Operations Research * Tour * Help * Chat * Contact * Feedback * Mobile Company * Stack Overflow * For Teams * Advertise With Us * Hire a Developer * Developer Jobs * About * Press * Legal * Privacy Policy * Terms of Service * Cookie Settings * Cookie Policy Stack Exchange Network * Technology * Culture & recreation * Life & arts * Science * Professional * Business * API * Data * Blog * Facebook * Twitter * LinkedIn * Instagram site design / logo (c) 2022 Stack Exchange Inc; user contributions licensed under cc by-sa. rev 2022.1.28.41306 Operations Research Stack Exchange works best with JavaScript enabled [p] Your privacy By clicking "Accept all cookies", you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy. Accept all cookies Customize settings