[HN Gopher] Counter-intuitive results in operations research
___________________________________________________________________
Counter-intuitive results in operations research
Author : sebg
Score : 76 points
Date : 2022-01-27 14:24 UTC (2 days ago)
(HTM) web link (or.stackexchange.com)
(TXT) w3m dump (or.stackexchange.com)
| kxyvr wrote:
| 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 wrote:
| Image of this example: https://imgur.com/a/Mjo1c0j
| wenc wrote:
| 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.
| cortesoft wrote:
| Bufferbloat is something that seems counterintuitive at first
| glance. Why would adding a bigger buffer hurt performance?
| digikata wrote:
| 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.
| tome wrote:
| 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.
| Aachen wrote:
| 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 wrote:
| I don't really feel like making a stack exchange account
| throwaway29303 wrote:
| https://apenwarr.ca/log/20170814
| pphysch wrote:
| Can analysis of bufferbloat help us understand the current
| state of the US/global economy?
|
| (Money = buffered economic value; too much liquidity =
| bufferbloat?)
| neffy wrote:
| 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.
| jl2718 wrote:
| 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 wrote:
| 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.
| gumby wrote:
| Palo Alto's traffic dept is quite good. Unfortunately they get
| overridden by the city council.
| satyrnein wrote:
| _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]
| realize wrote:
| Operations research is the art and science of obtaining bad
| answers to questions to which otherwise worse answers would be
| given.
| dqpb wrote:
| > 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.
___________________________________________________________________
(page generated 2022-01-29 23:00 UTC)