Counter-intuitive results in operations research | Hacker News Reader

Counter-intuitive results in operations research

or.stackexchange.com

133 pointssebg27 comments

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.

Image of this example: https://imgur.com/a/Mjo1c0j

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.

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.

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

2. Because we are all stupid occasionally, to one degree or another.

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.

Palo Alto’s traffic dept is quite good. Unfortunately they get overridden by the city council.

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.

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/185CohenHorowitzNat...

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.

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

Post an answer :)

Here it will get lost (semi-ephemerality is imo one of the disadvantages of HN), on stackexchange people will find it.

I don't really feel like making a stack exchange account

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.

Can analysis of bufferbloat help us understand the current state of the US/global economy?

(Money = buffered economic value; too much liquidity = bufferbloat?)

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.

I agree that debt is the underlying issue, but if we consider that the Fed's only solution to the "network issues" is to "increase the buffer sizes across the backbone" then perhaps "bufferbloat" is contributing to some of the supply chain issues.

And this would have logistical parallels with the just-in-time inventory strategy. which imho has been a maligned in that it does trade off other risks, but it also makes for better supply chain responsiveness (if the buffers are selected correctly on the right items).

Selecting appropriate buffer sizes is critical - a good set of comparisons there is what buffer would one want for streaming a movie vs a buffer for streaming a live video meeting connection.

JIT has been maligned by those who don't realise that in the original Toyota conception one's suppliers should be right there with you on site. Supply chains stretching across the oceans just aren't a thing in properly done JIT.

Well... part of the purpose of just in time is to surface problems quickly. Transient problems in an upstream process can be papered over by inventory on the receiving end, but when you remove that inventory everyone gets a clearer view of where the problem is, and everyone can do a better job of fixing it.

So just in time over the oceans works precisely as intended: it gives us information immediately when there is a problem. Whether or not it's within any manufacturers power to fix those problems is a separate issue.

(And I'm going to guess that there's no easy way to fix those problems, given that Toyota has opted for more inventory to hide those sorts of transient issues when it comes to certain parts.)

https://apenwarr.ca/log/20170814

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.

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

Could you elaborate?

I think GP means that it typically involves computationally intensive algorithms that then still give only an approximation.

> 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.

> 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.

Reply on news.ycombinator.com