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?

  • 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 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 at 17:17
  • @Raffzahn I'll see if I can find the video – dashnick Jun 7 at 17:20
  • 1
    Not sure of the paper, but maybe this is a fragment: imgur.com/wD4XFvD – mschaef Jun 7 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 at 0:49
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.

Your Answer

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 or ask your own question.