People – Page 2 – Mike Trick's Operations Research Blog

EURO Gold Medal

I am in Bonn, Germany for the EURO Conference. Tons of people here (2200+) but the organizers seem to be coping very well. Last night was a nice reception in a beer garden nearby. It has been a long time since I was at a conference with unlimited free beers. This morning was a little … slow.

The opening plenary session today included the announcement and talks of this year’s EURO Gold Medal winners: Jacques Benders, Eindhoven, and Frank Kelly, University of Cambridge. I missed most of the session (thanks, Graham Rand, for letting me know the winners), and I am really kicking myself for missing Benders’ talk: his work has a huge influence on my own current research. Benders’ Decomposition is one of the fundamental tools of operations research. Recently, people like John Hooker have breathed new life into the approach by introducing logical Benders’ decomposition (or combinatorial Benders decomposition).

Benders’ decomposition works as follows: take an optimization problem with two types of variables, x and y. First, solve the problem using only constraints that include just the x variables (this is the master problem). Give a solution x* to the master problem, now solve for the optimal y (the subproblem). We now have a candidate solution (x*,y*). The key step is to now generate a constraint on the x variables that says: “If you want a better x, it has to satisfy this constraint”. In classical Benders decomposition, that constraint is formed from the dual solution to the subproblem. In logical Benders, techniques such as constraint programming can be used to identify appropriate constraints. This iterates until the master problem (with the additional constraints) shows there is no better x than the ones already generated.

This approach can be radically faster than solving the overall (x,y) problem as one monolithic optimization. As the introduction to a reprinting of Benders’ original work says:

The real importance of the introduced algorithm is more evident today than ever before. It has had a profound seminal influence on the development of new generation of algorithms that enable us to solve ever larger and more complex from a wide spectrum.

I did get to the last half of Kelly’s talk. This was a very nice talk on modeling network routing, including issues of fairness. This happens a lot in internet routing of course, where routers try to figure out where things should go, and try to let everything through (eventually at least!). It would be rather annoying if one line through a router had a permanent “stop sign” while other traffic was sent through. Frank is famous enough to have a Wikipedia page.

Congrats to both Jacques and Frank, and no more missing plenary sessions for me!

Brenda Dietrich “Most Creative”

Fast Company has IBM Vice President, Business Analytics and Mathematical Sciences, Brenda Dietrich as number 27 on their list of “100 Most Creative People in Business”. Nice quote from her:

“Mathematics,” says Brenda L. Dietrich, 49, “is not mechanical. You’re finding how things look different on the surface and then seeing what they have in common underneath.”

It would be easy to put Brenda in the top 100 most brilliant or top 100 hardest working. It takes creativity to put her as one of the 100 most creative, and it is a creativity I am delighted to see. It can be hard to convince people that our field is primarily about creativity: rather than paintbrushes, we use mathematics to be creative.

Thanks to the INFORMS e-news for the pointer.

ACM Fellows and Operations Research

The ACM (the Association for Computing Machinery) has announced 44 new Fellows. A number of them are well-known in the operations research community (some are just plain well-known: can it be that Stephen Cook of NP-completeness fame was not a Fellow before now?). These include:

Tuomas Sandholm, Carnegie Mellon. Tuomas does an amazing number of things very well. He is an ideal faculty member raising money, training students, and so on. He also runs a company: CombineNet. Much, but not all, of his work is in combinatorial auctions, and he has really revolutionized that area. He also windsurfs. He is someone I am jealous of.
Michel Goemans, MIT. Has done amazing work in approximation algorithms. I am not a huge fan of approximation algorithms: I like solving real problems and it is not clear that a factor of 2 approximation is of much use, much less a log x/log log x approximation. And while many approximation papers give lip-service to the applications of the models they work with, very rarely are approximation algorithms implemented. That said, Michel does what I admire more than anything: he finds truly new and creative approaches to problems. When Michel finds a new approach (which he seems to do every two years or so), it is worth learning about because his approaches generally lead to a very rich a productive research vein. I am jealous of Michel too.
Sanjeev Arora, Princeton. Unlike Tuomas and Michel, I do not know Sanjeev personally, so I cannot be jealous of him. But I certainly know his work on randomized approaches to hard problems.

So congrats to all the new Fellows!

A New Honorary Doctorate

To me, honorary doctorates are things given to people much older than myself. For instance, my colleague Egon Balas received an honorary doctorate from the University of Liege. But Egon is a bit older than me (though I suspect he will be working long after I have shuffled off to some retirement community).

I was somewhat startled to hear (thanks to Pierre Schaus) that my friend, and, I had assumed, near-contemporary, though maybe he is much, much older than he looks, Pascal van Hentenryck received a Doctor Honoris Causa from the University of Louvain. What’s he got that I don’t got (other than an honorary doctorate)??? Let’s check the brief bio:

Pascal Van Hentenryck is professor of computer science at Brown University and the director of the optimization laboratory. Before coming to Brown in 1990, he spent four years at the European Computer-Industry Research Center (ECRC), where he was the main designer and implementor of the CHIP programming system, the foundation of all modern constraint programming systems. During the last 15 years, he developed a number of influential systems, including the Numerica system for global optimization, the optimization programming language OPL, and the programming language Comet which supports both constraint-based local search and constraint programming. Most of these systems are described in books published by the MIT Press and have been licensed to industry. He also implemented the generic abstract interpretation system GAIA.

Pascal is the recipient of an 1993 NSF National Young Investigator (NYI) award, the 2002 INFORMS ICS Award for research excellence at the interface between computer science and operations research, the 2006 ACP Award for Research Excellence in Constraint Programming, best paper awards at CP’03, CP’04, and IJCAI’07, and an IBM Faculty Award in 2004. He is the author of five books (all published by the MIT Press) and of more than 170 scientific papers. Pascal has a H-number of at least 38 in Google Scholar and his first MIT Press book has more than 1,000 citations.

Right…. OK… I guess there are a couple dozen things he has that I don’t have!

Congratulations Pascal on a very well deserved honor. I note that the other honorees were Professor Fert (Nobel Prize in Physics, 2007), Professor Rivest (Turing Award, 2002), and Professor Tsitsiklis (optimization guru). An amazing group, in which Pascal fits just fine.

Arnoff Lecture

I am just back from Cincinnati, where I gave the 17th E. Leonard Arnoff Memorial Lecture on the Practice of Management Science. When I look at the list of presenters, with my name on it, I am reminded of the Sesame Street tune “One of These Things (Is Not Like the Others)“. I was honored to be asked, and very happy to give the talk. There were about 85 in the audience, despite armaggeddon-like lightning and thunder outside.

The lecture is named after Len Arnoff, best known for his 1957 book “Introduction to Operations Research” with Churchman and Ackoff, one of the first (or the first) operations research textbook. He had a varied career: faculty member at Case and others, partner at Ernst and Ernst, and Dean of the Business School at the University of Cincinnati, before retiring to Florida in 1988. He died in 1991. (David Rogers is preparing a short biography of Arnoff, and I am grateful for the early version he sent me).

I was very pleased that his wife Ann flew up to attend the lecture, and that his daughter Susan could also attend.

The title of my talk was “Sports Scheduling and the Practice of Operations Research”. In addition to telling some stories about working with various sports leagues (you will have to attend one of my talks to hear those!), I spend some time on some of the technical issues. The main theme was that if you only knew operations research from ten years ago, you probably don’t have the techniques needed to solve real-world sport scheduling problems. In particular, the following methods don’t work very well:

“Routine” integer programming: let x[i,j,t] = 1 if i plays at j in time t, etc. etc. Weak formulation that does very poorly
Greedy heuristics. Generally do not lead to anything close to feasible.
Local search. Simple exchange generally leads to infeasible solutions, making it hard to use simulated annealing, tabu search or other metaheuristic approaches.

The following do make a big difference (and are much more recent ideas):

Complicated variables (like in branch and price): Let a variable represent a road trip, a schedule section, or a whole schedule for a team.
Large neighborhood search. Relax large pieces of a schedule and reoptimize keeping the rest fixed.
Constraint programming, ideally combined with integer programming, in order to quickly find feasible solutions.

Pulleyblank Lecture at Georgia Tech

Bill Pulleyblank, Vice President, Center for Business Optimization, IBM (I have written about CBO before) gave a talk at Georgia Tech on April 17. The title was “Computing, Business, and Operations Research: The Next Challenges”. Here is the abstract:

There have been two consistent drivers over the last sixty years of the evolution of computing: Computer power and price/performance improve by a factor of two every eighteen months; the problems that we wish to solve require this growth in capability and more. We seem to be reaching inflection points with both of these drivers. High performance systems are turning to massive parallelism to continue the required growth in performance. New challenges are arising in business and industry that require the solution of fundamentally different problems as well as the development of new approaches to old problems. Moreover, the rapid growth of a global economy has given an unprecedented urgency to dealing with these changes. I will review these subjects and some approaches that are being applied, with varying degrees of success. In particular, I will discuss five technical problems that must be solved to enable us to successfully meet the business challenges that we will face in the future.

Bill was a plenary speaker at INFORMS Pittsburgh 2006, and I thought his talk was one of the highlights of the conference. Georgia Tech has made a video and his slides available.

Balas Honorary Doctorate

My colleague Egon Balas just received an honorary doctorate from the University of Liege. Yves Crama, Director General of the School of Management, introduced Egon with a wonderful and heartfelt introduction. Some excerpts:

For more than 40 years, Egon Balas has been one of the pioneers of all major theoretical developments and of the most innovative algorithmic approaches in optimization. His name is linked to numerous approaches with esoteric names – disjunctive programming, polyhedral methods, « lift-and-project », « shifting bottleneck heuristic », … I omit many of them, since his research has been the topic of over 200 scientific publications.

Beyond his theoretical and methodological contributions of highest importance, Egon Balas has broadly contributed to demonstrating the usefulness of mathematical models in the practice of management, by carrying out numerous studies relating to the optimization of production in the steel industry, in transportation, in telecommunications, in the oil industry or in finance. The algorithmic developments that he has initiated, or with which he was closely associated, are nowadays integrated in many corporate software packages which enable managers to optimize the efficiency of their production processes, most frequently without a full understanding of the complex algorithms upon which they rely.

…

Before starting this brilliant academic career, however, Egon Balas had already spent, and turned the page of several fascinating lives. He wrote about them in a captivating autobiography entitled: “Will to Freedom: A Perilous Journey Through Fascism and Communism”. I strongly recommend reading this book.

Born in Romania from a Hungarian family, Egon Balas has joined the ranks of the Hungarian communist party and of the anti-nazi resistance during World War II. His autobiography retraces his arrest by the nazis, his imprisonment, the sessions of torture he went through, and his escape shortly before the arrival of the Russian troops.

After the War, Egon Balas rapidly ascended through the ranks of the Romanian ministeries, and held a diplomatic position in London before being arrested once again, this time by the Romanian communist authorities inspired by the bad example of the Stalinist purges in USSR. Two years of solitary confinement and of barbaric treatments were not able to break down this personality made of hard steel, who stubbornly refused to cooperate in the staging of a fake trial. Freed after the death of Stalin, but disenchanted by the excesses of the communist regime, Egon Balas started his new life as an economist and self-made mathematician in Bucharest.

This reminds me of my favorite Egon story. He was called to jury duty here in Pittsburgh and was asked, during routine questioning, “Have you ever been convicted of a crime?” “Yes”, he replied. “And what crime was that?” “Treason!”. He got out of jury duty.

Europeans do a nice job of honorary doctorates. Here in the US, honorary doctorates tend to go to executives who give $100 million to a university. In Europe, they go to people truly admired by the university. I mentioned this to Egon, who replied “Yes, but then again, no one gives $100 million to European universities!” I rarely best Egon in conversation.

Final Comments on Practice Meeting

I had to leave the INFORMS Practice Meeting Tuesday morning since I had to get back to do some teaching (it wasn’t a successful class: I can’t drive for four hours then teach!). So just a few final comments:

Brady Hunsaker gave a nice introduction to Open Source for OR, and attracted a good crowd (85 people by my count). I attended since I am on the strategic board of COIN-OR, one of the main open source initiatives for OR, but I am a bit fuzzy at times on the concepts. I find the whole licensing issue for open source to be one of the most frustrating. With more than 60 “open source” licenses to choose from, it seems that the goals of the whole movement are being drowned in legal minutia. Right now, the strategic board of COIN-OR is in the midst of an extremely long, detailed discussion of the conflicts between GLP (Gnu General Public License) and CPL (Common Public License). It is important since it is stopping wider distribution of some of COIN’s work, but it does seem like a minor variance in the number of angels on the pin. Brady didn’t sort that out, but he did give a good overview of what open source means and what is out there for OR. I think there is demand for more though: how does a company get into open source, and what are the pitfalls.
I liked the Stockholm social services Edelman presentation. My Mom just went to a nursing home, so the issue of providing home care to improve the quality of life of the elderly, and save costs by keeping people at home, hits very close to me. Not surprisingly, Sweden has a very extensive care network, to the extent that 60% of city workers in Stockholm are involved in social services. The presenters did a good job of outlining what looks to be a very powerful, flexible system.
I had a very interesting luch conversation on Monday with my table. INFORMS assigns people to tables at lunch, and asks those who have been involved in INFORMS or the conference (like me) to moderate the conversation. I had an interesting group, ranging in age from mid-twenties to sixties, with a wide breadth of experience. We spend most of lunch complaining about things: why isn’t OR better known? Why is education system in the US so bad? Who is going to learn mathematics in the future? Why are our tools so misused? Great fun!
I met Hari Balasubramanian, author of the Out of Kilter blog, albeit too briefly. He promises to get back to his OR blog: he has been concentrating on his history, literature, etc. blog.
I also chatted with Arnie Greenland from IBM, who told me about some of the wonderful things IBM is doing in text mining, particularly with the Social Security Administration (see this IBM page for a description of what they do). Arnie and I have worked on projects with the Internal Revenue Service and with the US Postal Service together.
Finally, it was great to see all the INFORMS staff. They aren’t always at the Practice Conference, but since Baltimore is the hometown for most of the staff, it was easy to get them all together.

I really like the Practice Conference: the presenters take their talks seriously, and it is very well done. And it gives great fodder for my MBA classes.

Chris Lofgren on “Hitting Potholes on the the Road to CEO”

If you are not at the INFORMS Practice Conference, you missed a plenary talk this morning that worth the price of admission alone. Chris Lofgren, President and CEO of Schneider National, gave a talk that was, at its heart, about being a successful OR professional, whether working as an analyst or working as a CEO.

I have known Chris since 1982 or so, when we started in the PhD program at Georgia Tech together. Chris could have been a successful academic (his work on scheduling flexible manufacturing systems still gets referenced) , but he chose a different path, and has been incredibly successful. He started at Semantech, then Motorola, but has spent most of his career at Schneider National, the largest truckload carrier in North America. Along the way he was the CIO, COO and since 2002 has been President and CEO (see the CIO magazine article on his path from CIO to CEO).

Chris credits his success, in part, to the skills and training he received in OR. “Not a day goes by that I don’t use the my education and background”, he said. Before the talk, he told me a story of talking to executives of a large retailer and noticing that the problem they were faced with could be solved by linear programming, and the duals actually would give the information they needed. It is nice seeing a CEO still thinking that way! Most of the time, of course, the OR background comes through in the analytical, data-driven way he makes the tremendous number of decisions a CEO must make.

His talked revolved around six themes:

Insight
Importance
Simplicity
Robustness
Breakthrough
Three Secrets (that aren’t secrets at all)

The talk was peppered with quotes and thoughts from his experiences. For instance, on insight, he noted that it was less important that a variable had a value than understanding why a variable had that value. Once you have that understanding, you are able to give senior executives the walk-away piece of information they need.

One point that really hit home was during his discussion on breakthrough: the need to understand things in perhaps radically different ways. As Chris said: “It is what you don’t know that you don’t know where you find the breakthrough”. During this discussion, he drew a distinction between “Making things better” versus “Making better things”. In operations research, we spend an awful lot of time on making things better: we improve schedules, we reassign work forces, we design transportation systems. And this is important! But even more important is to use the insights we have to create breakthroughs on processes and products to result in better things. The example he gave was a project we had worked on together for Motorola. Together, we figured out a better way to schedule a particular machine making printed circuit boards and we cut the time needed to make these boards by 10% or so, which saved the company millions. But the next step is one we could see: we gained insight into how to redesign the board to result in enormous savings. The redesign went against all the common wisdom, since it involved much more expensive components, but the system-wide savings would dwarf those immediate costs.

The “three secrets” that aren’t secrets are:

No one cares how smart you are (though Chris bonded with the audience by saying how smart us OR people are): people care about how you can help them … speak their language.
If you dare to make better things, you will push against the status quo and need courage in your convictions
There is no right way to do the wrong thing. Solve the right problem or don’t solve anything.

This summary can only give the bare bones of Chris’ talk. By backing up his thoughts with concrete examples from his experience (particularly his OR experience), he gave a talk that I found both insightful and inspiring!

Some Miscellany from the INFORMS Practice Conference

Some random things from today’s INFORMS Practice Conference:

Sanjay Saigal, popular columnist for OR/MS Today and founder/CEO of Intechne, formerly of ILOG, just to continue a theme, chided me for not pointing to his blog. I actually read his blog, but he normally blogs on non-OR things. It is great (with a great title): check out “Another Argumentative Indian”.
I met Sandy Holt, who had given me a blog idea. If you see me, don’t hesitate to say “hi!”: I’d love to meet more of you who have emailed me over the past couple of years.
I had a good long chat with Cindy Barnhart. Cindy is the current President of INFORMS, and is an associate dean of engineering at MIT. For a person who seems pretty laid back, she certainly seems to get a lot done!
I also had a long chat with Irv Lustig from ILOG. Irv is extremely upbeat about CPLEX at ILOG, just as Alkis Vazacopoulos is very upbeat about Dash and Fair Isaac. As OR becomes more mainstream (in a form known as “Advanced Business Analytics”, with “Business Analytics” being “look at your data!”), it is natural that the software firms would act more like businesses, being bought and sold, and having turnover. Perhaps I overly worry about the various changes.

OK, time for dinner and an early bedtime. My buddy from graduate school, Chris Lofgren, now CEO of Schneider is speaking first thing in the morning.