Month: August 2009

Homeland Security at the OR Forum

The OR Forum area of Operations Research has a new paper and commentaries published on the topic “Homeland Security: From Mathematical Models to Policy Implementation”.  The paper is by Larry Wein, with commentaries by Dick Larson, Eva Lee, Nathaniel Hupert (a doctor in public health) and Dave Alderson.  I think it is a very interesting article and very nice commentaries.  I particularly liked Dr. Hupert encouraging more of us in operations research to look at these problems:

What is needed is a new generation of engineers who can speak the language of health care (and vice versa), and who then step into the unknown in much the way Prof. Wein describes to discover the important unsolved (or avoided, as the case may be) problems.

I also enjoyed Dave Alderson’s querying of how to make this work. How do we get more people to have an effect on policy? He suspects it is not quite as easy as Larry makes it look.

Eva Lee talked about her work with the Centers for Disease Control on better systems for supplying emergency medical supplies, which I think is an extremely important and interesting issue. Dick Larson harkened back to World War II, and suggests we need a bit more social science to truly understand how people react in crisis.

I am the Area Editor for this, of course, and this is about the eighth OR Forum paper published. I like all of the papers, but I thought the commentaries on this one were particularly interesting.

If you have a thought on the paper or commentaries, may I encourage you to provide that at the Operations Research site? Hundreds (or thousands) of people download the paper and the commentaries, but we still don’t get much discussion there.

Good Day for the Tepper School

I am not at Mathematical Programming, but fearless blogger Tallys Yunes is, and he reported on the prizes given out yesterday (Tallys is also an example of the excellent students that come out of the Tepper School:  a theme for this post).  The Tepper School (Carnegie Mellon’s business school) did well, with Gérard Cornuéjols (faculty member at Tepper) winning the Dantzig Prize and Mohit Singh (recent graduate of our Algorithms, Combinatorics and Optimization Ph.D. program) winning the Tucker Prize.

The Dantzig Prize is given to the “one or more individuals for original research which by its originality, breadth and depth, is having a major impact on the field of mathematical programming.”   The amazing thing about Gérard is that there are a number of distinct lines of research for which he could have been awarded this.   In particular, he has done tremendous work in both integer programming and in characterizing and identifying various forms of matrices (ideal, perfect, balanced, and so on).  He has also found time to put together a book on Optimization Methods in Finance based on his very successful Masters level course here.

The Tucker Prize is the doctoral dissertation prize for the Mathematical Programming Society.  Mohit, now at Microsoft Research, did his dissertation with Tepper faculty member  R. Ravi.  Mohit has a number of nice papers on approximations for network design problems (and other things, including stochastic versions of hard combinatorial problems), using  new techniques he developed.  I am not normally a huge fan of approximation algorithms (“So our profits are within a factor of 3 of what is possible?  Umm….”), but I really liked Mohit’s disseration.  The iterative methods he developed are very powerful and might even have some practical use!  We have had an extremely impressive group of students come out of our ACO program, particularly since we only admit a handful of students every year among the three groups.

There are not too many universities left where serious mathematical programming is done in the business school:  I am proud to be part of one that is doing work at the very highest level.  The only downside is that once in while my dean complains that I should publish more:  “Look at your colleagues  Balas, Cornuejols, Ravi….” And I guess he is right, though that is a pretty tough standard to meet.

Added 11:20AM August 24. Turns out I hit the topics for Gerard’s prize correctly.  Here is the citation:

“You have been selected as the winner of the 2009 Dantzig Prize, in recognition for your deep and wide-ranging contributions to mathematical programming, including your work on Balanced and Ideal Matrices and Perfect Graphs and your leading role in the work on general cutting planes for mixed integer programming over many years covering both theory and computation.”

Not at ISMP

The International Symposium on Mathematical Programming of the Mathematical Programming Society occurs every three years, and I generally like to attend them.  They are like INFORMS conferences in size, but have many more talks (and people!) that I want to see.  This year’s ISMP is being held next week in Chicago.  Unfortunately, I won’t be there:  I will be in Cork Ireland attending an advisory board meeting of the Cork Constraint Computation Center.

If anyone is blogging from ISMP, please let me know so I can be sure to point to your entries.

Note added August 26. Check out the comments for pointers to Nathan Brixius and Tallys Yunes who are blogging the conference.

Social Engineering for the Overeducated

I got an interesting email today.  Ostensibly from Prof. Jochem Koos (a good Dutch name) from Elsevier, the email gives editorial and review policies for its journals.  After stating that referees must be of the highest quality, the letter then asks potential editors and reviewers to fill out a form to certify their credentials and be added to their list.   The bad part is that it costs $100 to be added to the list.  The good part is that referees are to be paid $30 per page reviewed.  $30!  I just finished a 50 page monster for an Elsevier journal.  I could get $1500?!  Wow!  Does that go for revisions too?  I could get that paper in an endless series of revisions at $1500 per round.  “There is a comma misplaced on page 26.  I will need to see a revision before I recommend publication.”    Ka-ching!  And if I am running a bit short on cash a few reviews of the form “Interesting paper but I would like to see it … 13 pages longer” should be just the thing for making the mortgage payment.

Of course, it is all a ruse.  Elsevier does not pay $30/page for refereeing (at least, not in operations research) and you don’t have to pay $100 to get on an approved list to referee.

It is surprising that a group that overwhelmingly has PhDs can be a target for such a scam.  On the other hand, considering some of the people I have met in my professional life, perhaps it is not that surprising.

Bottom line:  don’t send off $100 to just anyone with a gmail address.  Elsevier has some more information on these sorts of emails.

Competition then Cooperation: More on the Netflix Challenge

Wired has a nice article on the teams competing to win the Netflix Prize (thanks for the pointer, Matt!).  I think the most interesting aspect is how the “competition” turned into a cooperation:

Teams Bellkor (AT&T Research), Big Chaos and Pragmatic Theory combined to form Bellkor’s Pragmatic Chaos, the first team to qualify for the prize on June 26 with a 10.05 percent improvement over Netflix’s existing algorithm. This triggered a 30-day window in which other teams were allowed to try to catch up.

As if drawn together by unseen forces, over 30 competitors — including heavy hitters Grand Prize Team, Opera Solutions and Vandelay Industries, as well as competitors lower on the totem pole — banded together to form a new team called, fittingly, The Ensemble.

In fact, with a bit more time, all those groups might have come together:

As much as these teams collapsed into each other during the contest’s closing stages, they might have mated yet again to ensure that everyone on both qualifying teams would see some of the $1 million prize. Greg McAlpin of The Ensemble told Wired.com his team approached Bellkor’s Pragmatic Chaos and asked to join forces (he later clarified that he was still part of Vandelay Industries at this point), but was spooked by AT&T’s lawyers.“We invited their whole team to join us. The first person to suggest it was my 11-year-old son,” said McAlpin. “I thought it sounded like a really good idea, so I e-mailed the guys from Bellkor’s Pragmatic Chaos… [but] they said AT&T’s lawyers would require contracts with everyone to make agreements about who owns intellectual property… and it would take too long.”

Data mining methods can easily be combined.  A simple way is simply to have algorithms vote on the outcome.  This can often result in much better answers than any individual technique.  The Ensemble clearly did something like that:

To combine competitors’ algorithms, The Ensemble didn’t have to cut and paste much code together. Instead, they simply ran hundreds of algorithms from their 30-plus members (updated) and combined their results into a single set, using a variation of weighted averaging that favored the more accurate algorithms.

This is a great example of the intellectual advances that result from long-term “competitions”.  After a while, it is no longer competitors against competitors but rather all the competitors against the problem.  I don’t know if the Netflix Challenge was specifically designed to result in this, but it has turned out wonderfully.  It is much less likely that the groups would have gotten together if the contest was simply “Who has the best algorithm on August 1, 2009”.   The mix of initial competition (to weed out the bad ideas) and final cooperation (to get the final improvements) was extremely powerful here.

The winner announcement is expected in September.

Mittelmann’s Benchmarks CPLEX verus Gurobi

Hans Mittelmann has some new benchmarks comparing CPLEX 12.1 with GUROBI 1.1.2 on various mixed integer linear programming instances (I last wrote on these benchmarks last January with earlier versions of both codes:  be sure to check out the comments from that post since many of those comments apply to this also).  He covers both feasibility and optimization problems.

Checking the computation times for one set of optimizatin instances:

  problem     CPLEX1    GUROBI1     CPLEX4    GUROBI4
------------------------------------------------------
bc1            101         94         81         51
bienst2        165         58         87         27
dano3_5        148        618        276        362
mark._4_0      225         45         86         36
mark._5_0        f       6909          f       4368
mkc1             5        113          5
qap10           51         76         48         73
seymour1       178        285        116        161
swath2          13         10          5          6
swath3          26        563         49         53
30_05_100        7         11          4         11

The CPLEX1 and GUROBI1 use one processor; the …4 versions use 4.  The “f” means optimality was not proved in 7200 seconds (all times in seconds).   The above table is not representative, so be sure to check out Hans’ page.

A couple conclusions that I come up with (your mileage may vary):

  • Gurobi is a very impressive code:  whether CPLEX or Gurobi will be faster on a particular instance is not predictable, which is an impressive feat.
  • Parallel speedup is quite unpredictable.  Often there is no, or minimal, speedup;  sometimes there is huge speedup;  sometimes there is a slowdown.  None of this is surprising:  the initial linear relaxation is hard to parallelize, and the nondeterministic nature of tree search can lead to getting “lucky” or “unlucky” in the parallel search.

If we pull a few lines from the feasibility benchmarks:

============================================================
problem        CPLEX    FP-ab     FP-bfl    SCIP     GUROBI
------------------------------------------------------------
atlanta-ip      848        23        21       391       189
core4872-1529     1       413        52       374         1
ds                1         -      5350        38         3
germanrr        183        10         6       200        19
momentum1         1        23        17      6257         2
momentum2      6181        47        71      1504      4118
momentum3         1       350       627         -         4
msc98-ip        185        19        25      1754        33
neos16           47       236       241        43        72
neos-506428    1338      2969      4531      1739      2694

(FP are Feasibilty Pump approaches; SCIP is a fast non-commercial code).   Here the results are all over the map:  practically anything can win and anything can lose and there can be  three orders of magnitude difference between running times.

Now speed is not the only thing to look for in an optimization code (support, interfaces, price are a few other things to look at), but these benchmarks are very useful in trying to compare codes.  Thanks Hans!

Bluewashing Complete!

Two things happened to me last week with regards to IBM/ILOG (a topic I have written about quite a bit):

  1. I was on a conference call with an ILOG person and I said, jokingly, “Is that XXX from ILOG, an IBM Company?”.  His reply:  “Nope, just XXX from IBM”.  The “ILOG, an IBM Company” phrasing ended earlier this summer.
  2. I got an email from the PR people at ILOG (IBM, damn it, IBM!) saying in, essence, “Bluewashing for ILOG is complete”.   “Bluewashing”?  What the heck is that?  A web search suggests something about agreeing with the United Nations to not use child labor, but somehow I can’t see poor third world children toiling over ever-more-complicated polyhedral facets.

So last Thursday, I had a conference call with a number of IBM/ILOG people.  I don’t do many of these types of calls:  as is obvious from the blog, I am not a journalist, and I tend to get so caught up with the conversation that I don’t take notes or otherwise be anything other than an interested academic.  For instance, last spring, I had a wonderful private lunch with Pierre Haren (the CEO of ILOG turned Vice President at IBM).  Great conversation resulted in notes like “Optimization, constraint programming, integration”…  sigh…

Back to my call on Thursday.  “Bluewashing” turns out to be the phrase that IBM uses to describe the process of turning a new acquisition into part of IBM.  While the term sounds somewhat ominous, it seems much milder (anyone with an inside view to the contrary is welcome to comment!).  Once IBM owns code, for instance, it must be bluewashed to meet IBM standards.  If there is open source code included in acquired code, then it must be examined to determine if it meets IBM’s standards for using the code (is the license compatible with IBM usage and so on).  If not, then “bluewashed” code is substituted in.    IBM also has standard rules for things like academic licenses, so those had to be changed (made better, at least as far as support goes:  now academic licenses include full support).  People need to be “bluewashed” also, which I understood to mainly mean things like standardized benefits and so on (and not rubber hoses while the history of IBM is recited).

Coinciding with this is a change in corporate name.  ILOG is no longer “ILOG an IBM Company”;  ILOG is a brand name for a series of products that are part of IBM Websphere  (you can see this on the ILOG home page, where it used to say “ILOG an IBM Company”).  ILOG people are now simply IBM people.  Organizationally, things haven’t changed very much:  the former “ILOG people” are in an organization under Pierre Haren and have not been scattered throughout the IBM system.

A couple interesting aspects of my call.  Most of the conversation was with Lorenzo Delavegas who is lead of integration for the ILOG acquistion.   In a previous life, I ran the Carnegie Bosch Institute for Applied Studies in International Management, where one of the big research issues was how to successfully handle a merger or acquisition.  Most mergers and acquistions do not meet the rather rosy expectations that went into them, and many of them destroy shareholder value (see Daimler-Chrysler for an example).  IBM has specialists like Lorenzo oversee the integration of new companies to try to increase the chance of success.  Since he is not an operations research person, it was interesting to get his perspective on how ILOG fits within IBM.

The one phrase that was repeated multiple times was “stars lining up”.  It was obvious that the driver for IBM’s acquisition of ILOG was rules.  No one at IBM or ILOG has ever tried our intelligence by claiming anything else.  But optimization, in the form of CPLEX and the constraint programming software and in the people involved in creating and deploying that software, is now seen as a tremendous asset in IBM’s strategy, as shown in IBM’s Smarter Planet and IBM Business Analytics and Optimization.  These look to be great opportunities for operations research within IBM.  And from the call, I certainly feel pretty confident about CPLEX and the constraint programming codes as ILOG products from IBM.  Both the IBMers and ILOGers talked about how much easier it is to reach different communities through IBM.

I was also interested in how having CPLEX would affect IBM’s very strong support for open source, particularly through COIN-OR.  While I certainly did not get the feeling that the CPLEX team will be dropping everything to concentrate on open source efforts, I also ended up feeling that the acquisition is at worst neutral for open source optimization, and might well become an asset in time.

The ostensible reason for the PR call was the announcement of CPLEX 12 and other versions of ILOG’s software.  Most of this was announced at the INFORMS meeting in the spring (this is one reason to go to conferences:  you really do get a bit ahead of the crowd by being there).  The Excel interface has been changed since it was presented in the spring, I hear, so I look forward to checking that out.

It is not surprising that people on a PR call would be pretty upbeat about how things are going, but it was contagious.  IBM has always been strong in operations research, but I get the feeling that more of the company is seeing that strength.   And that can only be good for operations research.

My final comment for Lorenzo and the IBM group:  I would love to see the phrase “operations research” used in the Smarter Planet commercials!

INFORMS Podcasts on Crunching the Numbers

INFORMS (and its Director of Communications, Barry List) has been putting out podcasts on operations research oriented topics every couple of weeks for the past few months.  The title of the series is “Science of Better:  Crunching the Numbers”.  According to the site, this is:

A series of podcasts with unexpected insights into the way that math, analytics, and operations research affect people like you and organizations like your own. In every segment, an expert explains how he or she changed the world by crunching the numbers.

They now have a good collection of topics. The most recent podcast is with Larry Wein, who talks about homeland security, terrorism, and, of course, operations research.  Previous podcasts include a discussion on how analytics can help battle HIV/AIDS, how to understand the economy using supply chain concepts, how INTEL uses operations research to make decisions, and how to save on health care costs with OR.  I look forward to seeing what Barry has next for us!

At 20-30 minutes each, the five current podcasts are just the things to have on your mp3 player for long flights.

Data Mining and the Stock Market

As I have mentioned a number of times, I teach data mining to the MBA students here at the Tepper School.  It is a popular course, with something like 60% of our students taking it before graduating.   I offer an operations research view of data mining:  here are the algorithms, here are the assumptions, here are the limits.  We talk about how to present results and how to clean up data.  While I talk about limits, I know that the students get enthusiastic due to the not-insignificant successes of data mining.

We give students access to a real data mining system (SAS’s Enterprise Miner currently, though we have used SPSS’s Clementine Miner (now PASW, for some reason) in the past).  Invariably, students start putting in financial data in an attempt to “beat the stock market”.  In class, I talk about how appealing an approach this is, and how unlikely it is to work.  But students try anyway.

The Intelligent Investor column of the Wall Street Journal has a nice article on this (thanks Jainik for the pointer!) with the title: “Data Mining Isn’t a Good Bet for Stock-Market Predictions”.

The Super Bowl market indicator holds that stocks will do well after a team from the old National Football League wins the Super Bowl. The Pittsburgh Steelers, an original NFL team, won this year, and the market is up as well. Unfortunately, the losing Arizona Cardinals also are an old NFL team.

The “Sell in May and go away” rule advises investors to get out of the market after April and get back in after October. With the market up 17% since April 30, that rule isn’t looking so good at this point.

Meanwhile, dozens — probably hundreds — of Web sites hawk “proprietary trading tools” and analytical “models” based on factors with cryptic names like McMillan oscillators or floors and ceilings.

There is no end to such rules. But there isn’t much sense to most of them either. An entertaining new book, “Nerds on Wall Street,” by the veteran quantitative money manager David Leinweber, dissects the shoddy thinking that underlies most of these techniques.

The article then gives a great example of how you can “predict” the US stock market by looking at Bangledeshi butter production.  Now, I don’t buy the starkly negative phrasing of the column:  he (Jason Zweig) refers to data mining as a “sham”, which I think goes much too far.  Later in the article, he talks about what it takes to do data mining right:

That points to the first rule for keeping yourself from falling into a data mine: The results have to make sense. Correlation isn’t causation, so there needs to be a logical reason why a particular factor should predict market returns. No matter how appealing the numbers may look, if the cause isn’t plausible, the returns probably won’t last.

The second rule is to break the data into pieces. Divide the measurement period into thirds, for example, to see whether the strategy did well only part of the time. Ask to see the results only for stocks whose names begin with A through J, or R through Z, to see whether the claims hold up when you hold back some of the data.Next, ask what the results would look like once trading costs, management fees and applicable taxes are subtracted.

Finally, wait. Hypothetical results usually crumple after they collide with the real-world costs of investing. “If a strategy’s worthwhile,” Mr. Leinweber says, “then it’ll still be worthwhile in six months or a year.”

This is all good advice, and part of what I try to talk about in the course (though having the article makes things much easier).  My conclusion:  there is “sham” data mining, but that doesn’t mean all data mining is a sham.  I’d love to read the book, but the Kindle version is running at $23.73, a price that I suspect was set by data mining.