5 ms·

Counter-intuitive results in operations research

133 points by sebg 5y ago

jl2718 5y ago
I have a weak intuition that adding lanes to Alma and El Camino made the traffic problem worse, independently of the possible increase in traffic in the road. This is because it became impossible to do left turns into or out of the road, nor cross the road, without a traffic light, so they had to be installed at every intersection. Before the lane doubling, there was a slow-moving flow that was easy to navigate across, but after the lane doubling, there was either four lanes of high speed or a quadruple wall of cars. It also removed visibility because cars used to be able to pull out a bit before merging, but now they sit behind trees and pray nobody is coming in the right lane. Realizing this, the town tried to reverse or prevent Junipero Serra from being used as a fast double-lane road by installing a concrete serpentine across the middle and bike lane, with the obvious consequence of turning Saturday morning drives into a trolley problem. Good intention, but… maybe some paint instead. Sometimes I think Palo Alto might be a nicer place to live if the town lacked the budget to entertain new ideas.
- Lio 5y ago
  Braess's Paradox[1], mentioned in the article, is a wonderful observation on traffic flow. I was once told that "common sense is just what the stupid think is obvious without actually checking", which makes me chuckle[2]. All these counter-intuitive OR observations are wonderful because they remind us to dig deeper and measure stuff instead of guessing. 1. https://en.m.wikipedia.org/wiki/Braess%27s_paradox https://en.m.wikipedia.org/wiki/Braess%27s_paradox 2. Because we are all stupid occasionally, to one degree or another.
- satyrnein 5y ago
  independently of the possible increase in traffic in the road I don't see how this is possible with the same amount of total traffic; worst case the gaps are the same size, best case the cars are overlapped in the additional lane and the gaps are bigger. Unless you mean the same amount of cars per lane or something.
  - deleted 5y ago
    [deleted]
- gumby 5y ago
  Palo Alto’s traffic dept is quite good. Unfortunately they get overridden by the city council.
- twistedpair 5y ago
  I wish the fallacy of induced demands and its knock ons were accepted common knowledge, but alas I'm always disproven. People always complain that "it's so hard to get your section of town" when the visit. We know that. We don't widen the roads, or built new ones, because we know exactly what that will lead. Relish your steady state.
dqpb 5y ago
> 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. This is basic information theory. Counter intuitive == surprising == higher information content. This is also why fake news is so viral.
cortesoft 5y ago
Bufferbloat is something that seems counterintuitive at first glance. Why would adding a bigger buffer hurt performance?
- dtaht 5y ago
  Queue theory in general applies not just to supply chains, or bufferbloat, but explains a lot about how to do JIT and other forms of "traffic scheduling". Not enough people have read Len Kleinrock's wonderful books on this subject, and they are long out of print, and available only on archive.org. I wish it were taught more. His Queue Theory volume 2 is one of the most well-thumbed books on my bookshelf.
- Aachen 5y ago
  Post an answer :) Here it will get lost (semi-ephemerality is imo one of the disadvantages of HN), on stackexchange people will find it.
  - cortesoft 5y ago
    I don't really feel like making a stack exchange account
    - lucb1e 5y ago
      That's one of the best things about stack exchange: it's not a walled garden. You can post answers without creating an account and the added content is then available under creative commons.
- pphysch 5y ago
  Can analysis of bufferbloat help us understand the current state of the US/global economy? (Money = buffered economic value; too much liquidity = bufferbloat?)
  - neffy 5y ago
    It's not a bad idea per se, but no. The actual issue is too much debt, alongside too concentrated money. The issue at some level is some buffers are far too big, and 70% of the US population doesn't have any buffers at all.
kxyvr 5y ago
Unfortunately, I can't show a picture here, but I like one example in the introduction of Wolsey's book, "Integer Programming." It provides a short example of why rounding the answer from a continuous (LP) relaxation of an integer programming problem is not sufficient or even close to the integer optimal solution. Consider the integer program max 1.00 x1 + 0.64 x2 50 x1 + 31 x2 <= 250 3x1 - 2x2 >= -4 x1, x2 >=0 and integer As we can see from Figure 1.1, the linear programming solution (376/193,950/193) is a long way from the optimal integer solution (5,0). Personally, I like this example because it demonstrates that we need to be careful when working with integer optimization problems. It's not that rounding sometimes doesn't work. Hell, we use continuous algorithms like simplex when solving for integer solutions using things like branch and bound. However, it's not the same and depending on the application it can be dangerous to assume so. This also has implications for things like machine learning because they do use optimization algorithms to find their solutions and they often are based on continuous formulations used to give discrete results. It might work, but we should be really careful when it matters most.
- jamessb 5y ago
  Image of this example: https://imgur.com/a/Mjo1c0j https://imgur.com/a/Mjo1c0j
- wenc 5y ago
  Just chiming in here... I don't know that I would consider this counter-intuitive. Most introductory MIP textbooks make it amply clear that that IP and LP relaxations wouldn't be the same in general (except in special cases like when the constraint matrix is totally unimodular). Even so, sometimes LP relaxations with rounding can produce "good enough" answers if an IP solution is intractable in a reasonable time. Consider the Wolsey example; the optimal integer objective is 5.0, and the LP relaxation (376/193,950/193) objective is an optimistic 5.10, whereas the closest rounded LP relaxation (2,4) objective is 4.56. Even though the x may be in a completely different area than the integer optimal solution, it still manages to achieve roughly the same objective. So depending on the application, the rounded LP relaxation may just be good enough, especially in iterative processes (like control) where you just need to take baby steps toward a larger objective. It's not optimal, but it's not terrible.
realize 5y ago
Operations research is the art and science of obtaining bad answers to questions to which otherwise worse answers would be given.
- acaz 5y ago
  Could you elaborate?
  - lucb1e 5y ago
    I think GP means that it typically involves computationally intensive algorithms that then still give only an approximation.
amelius 5y ago
> 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. For any input? That's impressive.
aaron695 5y ago
mikewarot 5y ago
A decade or more ago, I had in my backpack a set of rubber bands, heavy thread, and paperclips that I did a demo with. If you suspended a weight from the thing with a removable paper clip joining one of the links, the load settled to a certain height. If you removed the clip (a negligible mass, in the demo), breaking the link (in a resettable manner for the next time), the load went UP, instead of down. I can't find the story that prompted me to make this demo back then, but here is an article from Nature that probably was the root source of it. https://lab.rockefeller.edu/cohenje/PDFs/185CohenHorowitzNature1991.pdf https://lab.rockefeller.edu/cohenje/PDFs/185CohenHorowitzNat...
- Too 5y ago
  This is also Braess paradox. Veritasium on Youtube has a good video about this, showing exactly your experiment, and comparing the phenomena with road traffic.

133 points by sebg 5y ago

I have a weak intuition that adding lanes to Alma and El Camino made the traffic problem worse, independently of the possible increase in traffic in the road. This is because it became impossible to do left turns into or out of the road, nor cross the road, without a traffic light, so they had to be installed at every intersection. Before the lane doubling, there was a slow-moving flow that was easy to navigate across, but after the lane doubling, there was either four lanes of high speed or a quadruple wall of cars. It also removed visibility because cars used to be able to pull out a bit before merging, but now they sit behind trees and pray nobody is coming in the right lane. Realizing this, the town tried to reverse or prevent Junipero Serra from being used as a fast double-lane road by installing a concrete serpentine across the middle and bike lane, with the obvious consequence of turning Saturday morning drives into a trolley problem. Good intention, but… maybe some paint instead. Sometimes I think Palo Alto might be a nicer place to live if the town lacked the budget to entertain new ideas.

Lio 5y ago
Braess's Paradox[1], mentioned in the article, is a wonderful observation on traffic flow. I was once told that "common sense is just what the stupid think is obvious without actually checking", which makes me chuckle[2]. All these counter-intuitive OR observations are wonderful because they remind us to dig deeper and measure stuff instead of guessing. 1. https://en.m.wikipedia.org/wiki/Braess%27s_paradox https://en.m.wikipedia.org/wiki/Braess%27s_paradox 2. Because we are all stupid occasionally, to one degree or another.
satyrnein 5y ago
independently of the possible increase in traffic in the road I don't see how this is possible with the same amount of total traffic; worst case the gaps are the same size, best case the cars are overlapped in the additional lane and the gaps are bigger. Unless you mean the same amount of cars per lane or something.
- deleted 5y ago
  [deleted]
gumby 5y ago
Palo Alto’s traffic dept is quite good. Unfortunately they get overridden by the city council.
twistedpair 5y ago
I wish the fallacy of induced demands and its knock ons were accepted common knowledge, but alas I'm always disproven. People always complain that "it's so hard to get your section of town" when the visit. We know that. We don't widen the roads, or built new ones, because we know exactly what that will lead. Relish your steady state.

dqpb 5y ago

> 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. This is basic information theory. Counter intuitive == surprising == higher information content. This is also why fake news is so viral.

cortesoft 5y ago

Bufferbloat is something that seems counterintuitive at first glance. Why would adding a bigger buffer hurt performance?

dtaht 5y ago
Queue theory in general applies not just to supply chains, or bufferbloat, but explains a lot about how to do JIT and other forms of "traffic scheduling". Not enough people have read Len Kleinrock's wonderful books on this subject, and they are long out of print, and available only on archive.org. I wish it were taught more. His Queue Theory volume 2 is one of the most well-thumbed books on my bookshelf.
Aachen 5y ago
Post an answer :) Here it will get lost (semi-ephemerality is imo one of the disadvantages of HN), on stackexchange people will find it.
- cortesoft 5y ago
  I don't really feel like making a stack exchange account
  - lucb1e 5y ago
    That's one of the best things about stack exchange: it's not a walled garden. You can post answers without creating an account and the added content is then available under creative commons.
pphysch 5y ago
Can analysis of bufferbloat help us understand the current state of the US/global economy? (Money = buffered economic value; too much liquidity = bufferbloat?)
- neffy 5y ago
  It's not a bad idea per se, but no. The actual issue is too much debt, alongside too concentrated money. The issue at some level is some buffers are far too big, and 70% of the US population doesn't have any buffers at all.

kxyvr 5y ago

Unfortunately, I can't show a picture here, but I like one example in the introduction of Wolsey's book, "Integer Programming." It provides a short example of why rounding the answer from a continuous (LP) relaxation of an integer programming problem is not sufficient or even close to the integer optimal solution. Consider the integer program max 1.00 x1 + 0.64 x2 50 x1 + 31 x2 <= 250 3x1 - 2x2 >= -4 x1, x2 >=0 and integer As we can see from Figure 1.1, the linear programming solution (376/193,950/193) is a long way from the optimal integer solution (5,0). Personally, I like this example because it demonstrates that we need to be careful when working with integer optimization problems. It's not that rounding sometimes doesn't work. Hell, we use continuous algorithms like simplex when solving for integer solutions using things like branch and bound. However, it's not the same and depending on the application it can be dangerous to assume so. This also has implications for things like machine learning because they do use optimization algorithms to find their solutions and they often are based on continuous formulations used to give discrete results. It might work, but we should be really careful when it matters most.

jamessb 5y ago
Image of this example: https://imgur.com/a/Mjo1c0j https://imgur.com/a/Mjo1c0j
wenc 5y ago
Just chiming in here... I don't know that I would consider this counter-intuitive. Most introductory MIP textbooks make it amply clear that that IP and LP relaxations wouldn't be the same in general (except in special cases like when the constraint matrix is totally unimodular). Even so, sometimes LP relaxations with rounding can produce "good enough" answers if an IP solution is intractable in a reasonable time. Consider the Wolsey example; the optimal integer objective is 5.0, and the LP relaxation (376/193,950/193) objective is an optimistic 5.10, whereas the closest rounded LP relaxation (2,4) objective is 4.56. Even though the x may be in a completely different area than the integer optimal solution, it still manages to achieve roughly the same objective. So depending on the application, the rounded LP relaxation may just be good enough, especially in iterative processes (like control) where you just need to take baby steps toward a larger objective. It's not optimal, but it's not terrible.

realize 5y ago

Operations research is the art and science of obtaining bad answers to questions to which otherwise worse answers would be given.

acaz 5y ago
Could you elaborate?
- lucb1e 5y ago
  I think GP means that it typically involves computationally intensive algorithms that then still give only an approximation.

amelius 5y ago

> 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. For any input? That's impressive.

aaron695 5y ago

mikewarot 5y ago

A decade or more ago, I had in my backpack a set of rubber bands, heavy thread, and paperclips that I did a demo with. If you suspended a weight from the thing with a removable paper clip joining one of the links, the load settled to a certain height. If you removed the clip (a negligible mass, in the demo), breaking the link (in a resettable manner for the next time), the load went UP, instead of down. I can't find the story that prompted me to make this demo back then, but here is an article from Nature that probably was the root source of it. https://lab.rockefeller.edu/cohenje/PDFs/185CohenHorowitzNature1991.pdf https://lab.rockefeller.edu/cohenje/PDFs/185CohenHorowitzNat...

Too 5y ago
This is also Braess paradox. Veritasium on Youtube has a good video about this, showing exactly your experiment, and comparing the phenomena with road traffic.