Month: July 2007

LinkedIn and Operations Research

Don Kleinmuntz of Strata Decision Technology and USC has made a concerted effort to get people in operations research to join LinkedIn. Since Don was a founding co-editor of Decision Analysis and has been Treasurer for INFORMS among many other jobs, he has an extensive contact list, and a number of us have joined. I was a latecomer, just joining today. Don so far has found it interesting, but he is holding back a decision on its importance.

I was surprised how many people were on it. There are dozens of “Trick”s alone, which is unusual. It definitely has cornered the market on 30-something IT people. But a search on “operations research” tagged 177 people, so it seems there are some of our type there (or just Don’s buddies!).

If you are on it, send me (Mike Trick) an invite and we can get our our little social network going.

Famous OR Ph.D.s and authors?

I see that Brian May, guitarist for dinosaur rock group Queen (“Bohemian Rhapsody”, “We are the Champions”, etc.) is finishing off his doctoral dissertation in astrophysics. Nice to have something if that rock ‘n roll thing doesn’t work out.

At the recent “Georgefest” celebration of George Nemhauser’s 70th birthday, dinner conversation (for Ralph Gomory, Tom Magnanti, and me) came to “famous operations research Ph.D.s”. Of course, the interest was not those famous for OR, but famous for something else. Here is what we came up with, augmented with a bit of web search after dinner (either with a Ph.D. or with a well known OR paper):

Gates and Lamarr aren’t really OR, but they are close. There are a number of famous economists with OR backgrounds (for instance, my friend Finn Kydland, 2004 Nobel laureate is really an OR person in the guise of an economist — trust me, Finn, that is is compliment!) but economics is pretty close to OR at times. So who else has an OR PhD or a paper in the OR literature but is better known outside of our field?

OR in Comics

I sometimes fantasize about writing the Great American Novel (New Zealand version).  In such a novel, naturally the hero would use operations research to achieve success and insight.  But when I think about such a novel, my imagination fails me:  how can I possibly make OR interesting in the context of fiction?

She:  Oh Biff, How can we ever be together?

Biff: Well, if I just solve this Traveling Salesman Problem using Concorde, I will be there as quickly as I can.

She: My hero!

Ummm…. no.  But the comic xkcd periodically has an OR theme, like solving knapsack problems.  You know you are a nerd when you solve the instance given by the comic (hint:  they better like fruit in one solution, but the solution is not unique).

Getting dumber?

Stephen Baker at Business Week points to a post by Jeff Jonas on how companies are generating so much data so quickly that companies can’t make sense of it, leading to “enterprise-amnesia“.  Both use this as a call for faster, smarter algorithms.  Now far be it for me to be negative about such a cry (I like algorithms!) but I think they are missing an important step in the process:  the modeling step.  Modeling is formulating the objectives, constraints, and decisions in order for the algorithms to go to work.   We’ve had lots of algorithms hanging around for decades that would address business issues, if only people would create appropriate models to use them.  Not every problem needs a fancy new algorithm!

Jonas’ blog has a number of interesting posts on things like persistent analytics.  This is all from a heavily information technology perspective, but OR should have a role to play in the issues he brings up.

Conference reviews, in perspective

I am just back from Prague: after another 36 hour travel marathon, I think it will take a day or so for my brain to catch up with me!

While I was gone, Scott Aaronson, a graduating doctoral student in quantum computing, had a brilliant article on computer science conference reviewing. From the 1936 Foundations of Computer Science (FOCS) review process:

Dear Mr. Turing,

We regret to inform you that your submission
“On Computable Numbers, With an Application to the Entscheidungsproblem”
was not accepted to appear in FOCS 1936. The Program Committee received a record 4 submissions this year, many of them of high quality, and scheduling constraints unfortunately made it impossible to accept all of them.

The reviews would be a great satire of computer science reviews except they are far too close to the truth:

—————————————- review 1 —————————————-

seems like a trivial modification of godel’s result from STOC’31

—————————————- review 2 —————————————-

The author shows that Hilbert’s Entscheidungsproblem (given a mathematical statement, decide whether it admits a formal proof) is unsolvable by any finite means. While this seems like an important result, I have several concerns/criticisms:

1. The author defines a new “Turing machine” model for the specific purpose of proving his result. This model was not defined in any previous papers; thus, the motivation is unclear.

See Scott’s post for the rest of this and for the other reviews. Many OR conferences are not reviewed (IFORS, EURO, and IFORS conferences accept practically anything submitted on time), but there are some that I am involved with (like CP, CPAIOR, MISTA, and PATAT) that have a review process, and it is clear that the review processes are very hit-and-miss.

With the exception of Scott’s ill-tempered diatribe against babies at conferences (perhaps as forty-something father of three-year-old, I am a little more sympathetic to the pressures of combining parenthood and academia), the entries in Scott’s blog are something I look forward to tremendously: he is opinionated, intelligent, amusing, and self-deprecating by turns, and generally teaches me something when I read him. He is about to join the faculty at MIT: lucky MIT!

IFORS Distinguished Lecturer

I am at the closing session of EURO. This year’s conference was huge with more than 2000 participants. I did attend a good amount of the conference, though Prague has its own attractions.

EURO (along with INFORMS, ALIO, and APORS) have a plenary given by the IFORS Distinguished Lecturer (I chair the committee that recommends the selection to the President of IFORS). This conference’s IDL is Bob Bixby, from Rice University and ILOG. Elise del Rosario introduced Bob, and here are some quotes from her introduction:

The IFORS Distinguished Lecturer for this conference is
Dr. Robert Bixby, an outstanding researcher, innovator, and business
leader. Dr. Bixby received his Ph.D. in the early 1970s from Cornell
University, and looked like he would have a long and distinguished
career in research on combinatorial structures. A sharp turn in the
1980s led him to develop CPLEX, an outstanding large-scale linear
program optimizer. CPLEX led to CPLEX Optimization, Inc, marketing
algorithms for linear and mixed-integer programming. CPLEX was sold
to ILOG in 1997, a company in which Dr. Bixby has served a number of
roles and where he is currently Chief Science Officer.

Dr. Bixby has combined his business success with continued research
success. He, along with his colleagues David Applegate, Vasek
Chvatal, and Bill Cook have just published a book entitled “The
Traveling Salesman Problem: A computational study” that sum up their
20 years of work on solving large scale traveling salesman problems,
culminating the solution of TSPs with tens of thousands of cities.

Dr. Bixby has held a number of leadership roles in our field,
including the presidency of the Mathematical Programming Society, and
has received a number of awards for this work, including the
Beale-Orchard-Hays Prize for excellence in computational mathematical
programming.

The title of his presentation was “From Planning to Operations: the Devil’s in the Details”.  Unfortunately, I had to run out for a plane (for my 42 hour return to New Zealand) so I only got to see the first part, where he reviewed progress in linear programming and integer programming.  A few striking points:

  1. The speed improvement in linear programming from 1996-2004 is a factor of about 5.3 million (3600 due to algorithms and 1300 due to computing).
  2. Not much improvement in linear programming the last few years:  only computer speed improvements.
  3. (Mixed) integer programming is about 13 times fast over the same period.
  4. The next version of CPLEX provides another decrease in time required (by a factor of .6)
  5. The next version of CPLEX is much better at finding feasible solutions to MIP (a test set of about 1300 instances) went from 250 with no solution found in 100 seconds in CPLEX 10 to about 120 in the next version.

The main point of the rest of the talk is that MIP and other optimization models are going to be used increasingly for day-to-day decisions (not as an aid to decision making, but making the decisions directly) and that puts lots of pressure on our models and data.

EURO Gold Medal winner

The EURO conference in Prague has begun. I really like Prague: it is a beautiful city with great bars, restaurants, museums, and even an OK english-language bookstore or two.

The first order of business here is the opening session (somewhat after the truly first, 8AM technical talks). Awarded at the opening session is the EURO Gold Medal, bestowed as follows:

The EURO Gold Medal is the highest distinction within OR in Europe. It is conferred on a prominent person or institution, for an outstanding contribution to the Operational Research science. The award is officially bestowed in conjunction with a EURO Conference, if there is a suitable candidate.

One advantage of having a conference at a university (along with such disadvantages as funny room layout, confusing directions and an air of “this isn’t what we normally do”: I will say the organizers have done a great job in making things as easy as possible with transit passes, lots of student helpers and so on) is available wireless. So I am in the auditorium, ready to announce the EURO Gold Medal first on the blogosphere.

And the laureate is Aharon Ben-Tal of the Technion, Israel. He works in continuous optimization, so I am not particularly well versed in his work. This is from his web page:

Prof. Ben-Tal’s research work is mainly in the area of nonlinear optimization. His theoretical work is concerned with extremum principles for problems in a general setting, with regard to the underlying decision space, and the underlying smoothness of the functionals. He was among the first to develop a comprehensive theory of second-order optimality conditions for nondifferential problems.

Prof. Ben-Tal is also involved in research in stochastic mathematical programming. He introduced the concept of entropic-penalty for problems with randomness in the constraints, and developed a duality theory which established a link between stochastic programming and the Expected Utility principle in economics. Recently he developed, together with Prof. A. Nemirovski, the Robust Optimization methodology. The focus of Prof. Ben-Tal’s work in recent years is in computational methods for solving large-scale continuous optimization problems. The algorithms he develops are used in designing optimally complex engineering structures, water distribution networks, and techniques for medical image reconstruction. The above projects are carried out in the MINERVA Optimization Center, a 2 million DM endowed research center.

Prof. Ben-Tal was a member of the International Council of the Mathematical Programming Society. He served as Area Editor of the journal Mathematics of Operations Research, and is currently a member of the Editorial Board of the journals Convex Analysis and SIAM Optimization. He received Awards of Excellence from the Technion both for research and for teaching.

The work with the most impact is the work he did with Nemirovski in creating the area of robust optimization.

On my way to Prague

I’m in the Hong Kong airport on the way from Auckland to Prague. I have about 22 more hours to go before I arrive at my hotel. It is great spending a year in New Zealand, but it is definitely a long way from anywhere!

Hong Kong airport is beautiful and incredibly well organized. I compare this to the alternative routing through Los Angeles, and there is absolutely no comparison. LAX is chaotic, rude, and very difficult (in my admittedly limited experience). Here, transferring flights involved no formalities at all: just a quick security check and into the departure areas, absolutely full of shopping, lounges, bars and restaurants.

I am on my way to the EURO conference. It is too bad this conference conflicts with the INFORMS “International” in Puerto Rico. Both are conferences I would like to attend. But the IFORS executive is meeting in Prague, so that is where I am going. I’ll try to provide an update or two along the way.