New CPLEX out

I got an email last week from a PR firm asking whether I would be willing to talk to some ILOG people about the upcoming release of CPLEX 11. Made me feel like a real journalist! Since I am unfortunately missing the Seattle INFORMS (the 12 hour flights from Auckland to LA are killing!), I was going to miss my normal chats with Irv Lustig and the gang, so I did talk with them a few days ago by phone.

You can read the press release about CPLEX 11. Since I have a few sports scheduling problems that are just not solving under CPLEX 10 (or anything else I have tried), I am looking forward to seeing if things are better under 11.

There were three things that struck me when talking to the CPLEX folks:

  1. Pretty well all of the improvements are in the integer programming parts, not the linear programming parts. This is in keeping with Bob Bixby’s talk at EURO (you can see a version of the talk in Seattle, too) where he said that LP improvements were enormous from 1996-2003 but not much has happened in the last few years.
  2. The improvements in mixed integer programming in this version are coming from improved search. This contrasts with previous improvements that came from better cuts. So, when CPLEX went from version 6 to 6.5, there was a huge improvement in speed due to the addition of Gomory cuts. I would guess that in the academic world, search has received about 1% of the attention that cuts have gotten. There is a well defined theory of facets, cut generation, and so on, and very little general insight into search. CPLEX 11 uses something ILOG calls “dynamic search”. If you use dynamic search, you have to give up all the callbacks that are normally used to provide user-defined search, so you are accepting the ILOG “black box” on search. This should lead to some pretty interesting testing: can problem-dependent search do better than the general search approach? The constraint programmers have always had search as a key component to their systems; it is about time integer programmers spent more time thinking about it. Is it possible to put search on the same solid foundation that cut generation is? Or will search end up being just a bunch of heuristics that happen to work well on many instances?
  3. Parallel is getting more attention (and parallel linear programming may be the step that makes LP faster). But it is clear at this point that having 8 cores (as I do!) won’t result in 8 times speedup. First, the root node isn’t parallel, so anything with an expensive root node won’t see much improvement at all. Later, once the branch-and-bound search tree is in full swing, the amount of memory access needed is large, so the bottleneck occurs in the pipe to the memory. I got the impression that this is something they are working on, which is good: lots of the upcoming speed improvements are going to be in parallel computing rather than higher clock speeds.

There are other new aspects to CPLEX 11 on the usability front, most notably the ability to generate all optimal solutions, not just one, which seems like a useful feature.

ILOG has put together some forums on optimization and constraint programming. If you hurry, you can be the first to post to them!

Aurelie Thiele on Operations Research

Aurelie Thiele of Lehigh has a wide-ranging blog on “Thoughts on business, engineering and higher education”. Many of her posts are on operations research. I particularly liked her thoughtful piece on the role operations research plays in the Grand Challenges in Engineering. The leadership of INFORMS put together a white paper on the subject, which I wrote about a while ago. Aurelie takes issue with the fragmented aspect of the proposed role:

The applications-driven paper lacks the unifying theme that a focus on information management would have provided, and instead OR comes across as an add-on to other people’s expertise – certainly valuable, but not critical. I’m not sure why anyone would want to be portrayed as jack of all trades but master of none… The authors also miss the opportunity to portray operations researchers as the center of inter-disciplinary teams bringing scientists from various disciplines together, drawing from their experience in one area to help researchers in another. When I finished reading the paper I wasn’t particularly excited to be working in the field, but I give the authors credit for trying – marketing OR is an uphill battle, given the aversion to math of most regular folks, and every little thing helps.

I have been struggling with many of this very issue during my year in New Zealand (since I have had the opportunity to give a number of “big picture” talks). Is OR just a collection of tools that we jealously guard or is there more commonality amongst us? And are we critical, or just a bit of sprinkle on top of the ice cream sundae? Of course, I remain excited by the field, and reading the rest of the blog, I think Aurelie does also.

Aurelie has been blogging since March: I can’t believe it took me so long to stumble across this excellent blog. Check it out!

Sheldon Jacobson and OR Videos

The October, 2007 issue of OR/MS Today has a short article by Sheldon Jacobson of the University of Illinois on creating videos about the work he and his lab does. There are two videos: one on pediatric vaccines and one on airline security (I love the variety of work you can do in OR!) (they are a little slow-loading). It is too bad that they aren’t YouTube videos, where more people can see them (and the technology allows better incremental loading), but I am extremely impressed with the professionalism that went into the videos. Of course, it is not cheap:

When it comes to video production, you get what you pay for. As a rule, the videos cost $1,000 per minute of the final product. Using a cell phone camera to film yourself speaking about your work will result in predictably poor quality. The professionals in the video production industry — the producer, videographer and editor — have a wealth of experience (and some interesting tricks of the trade) to make you and your work come to life.

Check out Sheldon’s page for more about the impact this work (and others he has done) has had.