Month: November 2007

Not at INFORMS

I’m not at this year’s INFORMS meeting.  No, it is not because I am in a snit because it looks like Seattle is going to beat the attendance record Pittsburgh set last year (I predicted it, and predict that Washington will set a new record next year that will take a few years to break).  I’m not going because it is 18 hours of flights away from New Zealand, and I needed to cut back on my travel a bit.

So I won’t be live-blogging the conference.  Laura McLay of “Punk Rock Operations Research” will be there so look for her.  If there are any other OR bloggers at the conference, let me know so I can follow the conference vicariously.

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!