Enviable Problems: MIP and Warren Buffett

There’s been some recent talk about just how awesome Warren Buffett actually is. Summary: “What have you done for me lately?

Warren Buffett has an enviable problem: how to get superior return on a shit-ton of money. For someone with Buffett’s skills, there are many high-return opportunities out there. The “problem” is that most of those opportunities are not of a sufficiently large scale to make an impact on Berkshire’s bottom line. A 100% return on a $1M investment would mean a lot to me, but not so much for Warren. In other words, the opportunities in the upper right corner are the ones he’s looking for:

Warren

Erwin recently posted to a link to a paper by Bob Bixby from Gurobi about the history of mixed-integer programming (MIP) solvers. The MIP community has more in common with Warren than they realize! Bixby has a nice table that summarizes improvements in MIP solver performance from 1998 – 2004:

Speedup
Algorithmic improvement (machine independent) 3300×
Machine improvement 1600×
Total improvement 5,280,000×

That’s a pretty good ROI. The challenge is how to continue to find these kinds of speedups. The Gurobi team thinks about this a lot. Ed drew me this picture once:

MIP

There are lots of MIP improvements that provide dramatic speedups. The problem is that they only apply in certain specialized circumstances (e.g. a certain kind of network model). In fact, since many optimization problems can be written as MIPs, many, many OR papers can be viewed as clever ways of speeding up certain weird subclasses of MIP. (My thesis is an example, even though I never really thought of it that way.) On the other hand, there are also improvements that apply to a large percentage of MIP models but yield a relatively modest benefit (for example certain presolve rules). The game is to find improvements that provide large speedups for large classes of MIP models. Again, the upper right corner is where you want to be. Bixby’s paper supplies some examples: dual simplex, presolve, and so on.

It’s hard to climb at the same rate as the air gets thinner. Kudos to those who have the stamina to keep going.

Author: natebrix

Follow me on twitter at @natebrix.

1 thought on “Enviable Problems: MIP and Warren Buffett”

  1. Some of the tricks that speed solution of some models actually slow the solution of others. (Trivial example: decomposing a small model.) This also seems to be true of some “general” algorithm improvements. The previous version of solver X may actually be faster than the new version on some (presumably a minority) of your problems.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s