2

A few years ago, I remember seeing a video of Ray Kurzweil discussing how linear programming was an example of how software (algorithms) - independent of hardware - is also getting faster (exponentially) over time. He referenced a paper on this topic I believe that showed the historical speed increase on constant hardware.

I can't seem to find this paper, however. Is anyone aware of it?

Improve this question
6
  • 4
    Not aware of the paper but I am skeptical about such claims. I have seen an inefficient algorithm written in an interpreted language running on modern hardware outrunning an efficient algorithm in a compiled language on ancient hardware. Sometimes, the speed of the hardware masks the inefficiency. Sometimes it is just memory addressing which was not available on ancient hardware. You need to compare like with like to assess what the author claims.
    – cup
    Jun 7, 2019 at 16:33
  • Mind to specify 'a few years ago' and add more information about the source and how this is RC related and not a question better suited on SO or HSM.SE ?
    – Raffzahn
    Jun 7, 2019 at 17:17
  • @Raffzahn I'll see if I can find the video
    – dashnick
    Jun 7, 2019 at 17:20
  • 1
    Not sure of the paper, but maybe this is a fragment: imgur.com/wD4XFvD
    – mschaef
    Jun 7, 2019 at 19:20
  • 1
    @cup I'm not skeptical at all, having actually been working on this sort of stuff for decades. But you are right that it is hard to make meaningful comparisons over a 30 or 50 years timescale, because the size of problems that are now routine were completely out of reach of 30 or 50 year old computing hardware. (But my knowledge of the state of the art in linear programming is zilch, so I can't answer the OP's question!)
    – alephzero
    Jun 8, 2019 at 0:49

1 Answer 1

Reset to default
8

See Robert Bixby, "Solving Real World Linear Programming Problems:A Decade and More of Progress."

https://doi.org/10.1287/opre.50.1.3.17780

This paper compares a 1980's version of the CPLEX solver on old and new hardware with a contemporary (the paper was published in 2002 or 2003) version of CPLEX on contemporary hardware and finds that Improvements in the code and the hardware each contributed 3 orders of magnitude to speed.

The paper includes a useful history of LP solvers back to the 1960's.

There have been several follow up papers and presentations by Bixby and colleagues from GuRoBi.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .