In New York doing Mixed Integer Programming

I am in New York at Columbia University, attending the Mixed Integer Programming (MIP) workshop. This workshop series was started about 5 years ago, and has grown into a hundred person workshop/conference. It is still run pretty informally (no nametags: I guess it is assumed that everyone knows everyone else. Having just shaved off my beard, I would prefer letting people know my name rather than relying on their ability to recognize me!).

So far, the most interesting aspects have been approaches much different than current practice. Rekha Thomas of the University of Washington had a very nice talk on a variant of Chvatal Rank (called Small Chvatal Rank) which involved using Hilbert basis calculations to find normals of facets of the integer hull (you can think of this as Chvatal rank independent of the right hand side). I’m not sure if it is useful, but it certainly generated a number of neat results. Peter Malkin of UC-Davis talked about using systems of polynomial equations to prove the infeasibility of problems like 3-coloring. I have seen versions of this work before (given by coauthor Susan Margulies) and always begin thinking “this can’t possibly work” but they are able to prove a lack of 3-coloring for impressively large graphs.

One of the most intriguing talks was given by John Hooker, who is exploring what he calls “principled methods of modeling” (or formulation). John has a knack of looking at seemingly well-known approaches and seeing them in a new and interesting way. It is not yet clear that this principled approach gets you anything that is not folklore formulation tricks, but it is interesting to see a theoretical underpinning to some of the things we do.

Postscript. Now that I think about it a bit more, John did present a problem that would have been difficult to formulate without his principled approach. I’ll try to track down an explanation of that example.

Personal Blogs, Personal Views

William Patry, Google’s Senior Copyright Counsel, is ending his blog “The Patry Copyright Blog“. That sentence, in short, gives one of the two reasons he is ending the blog (the other is the horrid state of copyright law, in his view). Patry is a long time copyright lawyer who started the blog while in private practice. Once he joined Google, however, suddenly people projected his blog onto Google. Of course, it is hard to see how to refer to people without saying something about their credentials. Saying, “William Patry, Google’s Senior Copyright Counsel, said this on his blog” seems to give more credence to a view than “William Patry, random guy on the street, said this”, even without making the step to “Google as a company believes this”. But too many people make the last step, making it impossible for Google’s senior copyright counsel to have a personal blog.

I’m primarily an academic, and there seems little harm in referring to me as “Michael Trick, professor at Carnegie Mellon, said …”, since there is a long tradition of celebrating individual views among professors. If everything a university professor said had to be vetted by the university (and who in the university could do such a vetting?), you wouldn’t hear much from professors on any topic. Once in a while, I get identified with organizations. Recently, I was referred to as “Michael Trick, former President of INFORMS” in a blog entry where I have pretty well convinced myself I was not referred to as a “nut with a computer” (though some doubt exists), which is a bit more troublesome. Even in 2002 as President of INFORMS, almost nothing I said was speaking on behalf of INFORMS. Certainly now, if it is not obvious, I don’t speak for INFORMS.

This is also relevant to the recent IBM/ILOG acquisition. We’d all love to hear from the ILOGers and IBMers on what they think it means. I would love to hear it on a personal level on how it will affect their life, their work, our field, and the universe. But it is essentially impossible for anyone at IBM or ILOG to speak personally at this point. Anything they say could be taken as “official” and would draw harsh legal (and company) repercussions. So, until the acquisition is complete, I think we will have to be satisfied with carefully crafted, legally-cleared, official comments.

Traffic Behavior and Operations Research

mergingThe New York Times Magazine has an article today entitled “The Urge to Merge” on how people handle tunnels, construction, and so on, when driving, where the number of lanes decreases. Some people, the lineuppers, carefully get into one of the continuing lanes and wait patiently to go through the tunnel. Others, the sidezoomers, zip along one of the ending lanes until the last minute, and then force themselves into the lane. Of course, whether they can merge in depends on the mood and attention of the lineupper involved. All this leads to aggravation and, worse, inefficiency, since the constant stop-and-go allows less traffic to flow through than a smoothly flowing system.

When I lived in Germany, traffic patterns were noticeably more organized (as was much of life). There, cars all go up to the merge point, at which point the cars alternated in the use of the lane. This “zipper” effect could be done at reasonably high speed, since there was never any question on whose turn it was. The only worry was some silly American messing up their system (at which point I got to learn lots of German words that were not taught in my classes). This is a great example of the value of coordination. Almost any solution where people each know what the others will do is better than uncertainty.

My only complaint about the article came in the following part:

So I started consulting professionals on my own: traffic engineers, the highway police, queuing theorists. The learning curve, it must be said, was robust. I hadn’t known queuing had theories. But of course it does, mathematicians and business-operations people have to work them out, the heart-attack patient gets in ahead of the sprained ankle and nobody has a problem with that, and anybody who has been to Europe intuitively understands what one engineer meant when in midsentence he said to me, “perfect England,” meaning culturally mandated compulsive queuing, and, “perfect Italy,” meaning culturally mandated compulsive nonqueuing.

Operations Research, dammit, Operations Research!

Word from ILOG on CPLEX

John Gregory, ILOG CPLEX Product Manager, posted this on sci.op-research:

The July 28 announcement of the agreement by IBM and ILOG was a surprise
to all but a few key members of the two companies. It will take literally
months, not days, before this transaction will be completed. Until then
an arm’s-length relationship must continue to exist between IBM and ILOG.
For these reasons, speculation about specific future product direction is
fruitless. The respective teams at IBM and ILOG have not yet even had time
to digest the news themselves. IBM and ILOG both have long histories of
supporting the OR community and leadership in that community. I have been
assured by an executive involved in the transaction planning that IBM
is keenly interested in CPLEX and the optimization products, and keenly
interested in preserving the business it generates and the customer
goodwill that this business has developed over the past 20 years. ILOG’s
optimization technology and technologists were considered a key asset in
the transaction.

John Gregory
ILOG CPLEX Product Manager

I agree about the leadership history of ILOG and IBM. Both as companies and as individuals within those companies, they have had a tremendous positive effect on our field. I look forward to company statements aimed not at the financial world (“This is a good acquisition for both IBM and ILOG”) but at the OR world. And I am sure those will be coming in time.

More on IBM/ILOG

Lots of activity on the IBM purchase of ILOG, with most concentrating on the business rules aspect, which seems to be a driving force. A reader, in a comment, pointed to an article from InternetNews, quoting IBM’s Sandy Carter, VP of SOA (see: Ratliff was right. SOA is important!). Here is what Sandy says about optimization:

Meanwhile, IBM’s Center of Business Optimization, a group of consultants acquired when IBM bought PricewaterhouseCoopers Consulting for $3.5 billion in cash and stock in July 2002, uses Ilog’s optimization products heavily, Carter said. She noted that consultants can now more fully leverage tools such as Ilog CPLEX and CP Optimizer.

Besides not quite matching up with my memory of where IBM’s Center for (not of) Business Optimization originated (I visited Bill Pulleyblank, VP of the Center and a long time IBMer, not PwCer, and his group a couple of years ago), this description of how owning CPLEX can help IBM is a little worrying. The nice thing ILOG (and Dash) did as independents was to push optimization widely. Everyone should have some integer programming in their lives! Now, the two major optimization software systems are owned by companies that could stress consulting and services, not products.

Here are a couple of futures:

  1. The full weight of IBM’s research and marketing arms is thrown behind products like CPLEX, improving the software and selling it far and wide, or
  2. IBM realizes that it has a great competitive advantage in using CPLEX for projects that it is involved with, making it advantageous to limit the availability of the software.

I hope very much that the outcome of this is the first scenario. When I talked to Pulleyblank a couple of years ago, he very much wanted to create optimization products to sell, which is an encouraging sign for the future.

IBM to acquire ILOG

News from IBM: they are set to acquire ILOG. Among other things, ILOG makes CPLEX, one of the best linear and integer programming codes out there. Together with the previous purchase of Dash by Fair-Isaac, this means much of the operations research software world has changed hands in the last few months. It is interesting that most of the announcement is about rules, not optimization:

When completed, the acquisition of ILOG will strengthen IBM’s BPM and SOA position by providing customers a full set of rule management tools for complete information and application lifecycle management across a comprehensive platform including IBM’s leading WebSphere application development and management platform.

BPM allows companies to model, automate, monitor, and redesign business processes, such as opening a bank account, documenting a medical record, or customizing an insurance policy. It enables companies to improve customers’ service and increase efficiency, automation and accuracy. Using BPM, companies can examine tasks within an organization – particularly those done manually or involving significant document processing – and apply BPM to automate or streamline them. Such processes are becoming increasingly critical as business operations become more complex and information volumes grow at phenomenal rates. Building on IBM’s existing capabilities, ILOG will help customers manage change and complexity in their business processes by providing powerful, yet easy-to-use business tools.

For example, a business rule might be applied to elevate a premier customer to the front of a phone queue as part of a customer service process. ILOG’s Business Rule Management System provides users with tools that allow greater control over the criteria that determine how and when to route those premier customers. As such, businesses can accelerate the process of initiating policy changes that may be driven by market trends or competitive activity to ensure customer satisfaction is maintained.

ILOG technology has the potential to add significant capability across IBM’s entire software platform and bolster its existing rules management offerings. This includes improved rules and business optimization capabilities for Information Management offerings, better visualization for Lotus products, enhanced optimization within Tivoli solutions, and efficient supply chain management assets for planning and scheduling.

Stay tuned for the effect this has on CPLEX and the optimization world.  Note that this combination has to step through some regulatory hurdles, so it will be a few months (end of the year?) before ILOG people become IBMers.

Passing of Randy Pausch

Randy Pausch, the Carnegie Mellon professor whose “Last Lecture” led to a book and world-wide attention, passed away today from pancreatic cancer. From a message from Jared Cohon, President of CMU:

Randy captured the minds and hearts of millions worldwide with his Carnegie Mellon lecture, “Really Achieving Your Childhood Dreams,” and his book, “The Last Lecture.”

Randy, who earned his doctorate from Carnegie Mellon in 1988, returned to the university in 1997 as an associate professor of human-computer interaction and computer science. Along with Carnegie Mellon Professor Don Marinelli, Randy was the co-founder of the Entertainment Technology Center, a leading interactive multimedia education and entertainment center.

At Carnegie Mellon, Randy was also the director of the Alice software project, a revolutionary way to teach computer programming. The interactive Alice program teaches computer programming by having kids make animated movies and games. A fitting legacy to Randy’s life and work, Alice may in the future help to reverse the dramatic drop in the number of students majoring in computer science at colleges and universities. Randy was also known as a pioneer in the development of virtual reality, and he created the popular Building Virtual Worlds class.

An award-winning teacher and researcher, Randy was also a National Science Foundation Presidential Young Investigator and a Lilly Foundation Teaching Fellow. He used sabbatical leaves to work at Walt Disney Imagineering and Electronic Arts (EA), and he consulted with Google Inc. on user interface design. He is the author or co-author of five books and more than 70 articles.

Perhaps the greatest lesson, however, Randy taught us all was how to live, even in the face of great challenges, and how to follow our passion. While Randy’s greatest passion was clearly his family, he did not shy from sharing his passion for his work as a professor, for his students, and for Carnegie Mellon. We will miss Randy, but we will carry the memory of him and all that he did to make Carnegie Mellon a better university and each of us who knew him a better person.

I didn’t see Randy’s original talk, though I have seen videos of it. I don’t know how he had the strength to make a talk like that. If I had brought my wife and son out on the stage knowing I would not see him grow up, I would be a weepy mess. I am sorry to see his passing, but I think a lot of kids got extra hugs, and perhaps people better balanced their lives (and lived out their childhood dreams), because of him.

Don Ratliff at IFORS

Mike Trick and elephant at IFORS 2008So what happened to my “live blogging” at IFORS 2008? Well, unfortunately I had an administrative role at the conference (nothing like the real work of Hans Ittmann and John Bartholdi, but a role none-the-less) and that took time. And I am always a believer in the “social networking” aspects (read: hanging out at the bar with friends), and that takes time. And I did go on one of the famous IFORS outings, where I got sucked at by an elephant. Finally, I spent 3 days at the end at a lodge with no internet connection (technically, there was an internet connection, but I pretended it didn’t exist). Put it all together, and I fell a bit behind. But here are some notes that I took along the way.

Don Ratliff at IFORS 2008The Tuesday plenary speaker was my co-adviser from 20 years ago, Don Ratliff from Georgia Tech. Don has had a great career, both in academia and in business. He was editor of Operations Research for a while, and published a number of interesting papers. He also founded CAPS Logistics, which was later bought out by Baan in a rather confusing and lawsuit-laden muddle. The title of his talk was “The Role of Operations Research in Lean Supply Chains”. He began by drawing an analogy between lean production and lean supply chains. In his view, lean production involves three main components:

  1. Eliminating waste. Waste can be in terms of inventory, or time, or anything else that is not needed to meet the ultimate end of production: producing the thing!
  2. Synchronizing flow. Getting things to where they need to be at exactly the right time.
  3. Continuous improvement. Production environments are not static, and there is the opportunity for improvement as processes change.

He suggested that there has been insufficient effort to adopt these precepts throughout the supply chain. Partially this is a result of the multiple actors within a supply chain. It is typically easier to say “do this” within a factory with a common boss; supply chains often have multiple people involved, including the customer, making it harder to do things like waste removal and synchronization. But there are significant savings possible, making things worthwhile.

I thought the most interesting point he made came under the area of “continuous improvement”. He pointed out that ERP (Enterprise Resource Planning, the SAPs and Manugistics of the world) have shut OR out. It is hard to improve part of the system, when that part is embedded in a larger whole. In essence, OR has missed out of ERP, so nothing much has changed in OR since the PC (which did have an effect on the OR world and thinking). But he identifies SOA (Service Oriented Architecture) as a great new opportunity for our field. Quoting from wikipedia:

Service-Oriented Architecture (SOA) is a software architecture where functionality is grouped around business processes and packaged as interoperable services.

It is through these services that OR can have its strongest effect. If you have a better routing system, you can embed that in the routing service of the SOA system, improving that aspect without affecting the rest of the system. This is exactly what is needed for continuous improvement, and exactly what OR is good for.

Within OR, we often don’t track IT concepts such as SOA or business intelligence, but we should: it can have a great effect on how our work is used in organizations.

I thought this was another very good plenary, and again the audience seemed quite engaged with in.

Opening Session at IFORS

IFORS 2008 BannerAfter a somewhat rocky start (an electricity substation in Joburg failed, resulting in large traffic delays, so the student assistants were late so the rooms didn’t have computers on time), the IFORS conference officially opened with a fantastic opening session. Of course, I am biased, since I am on the IFORS board with responsibility for meetings. But I do think it went very well.

IFORS 2008 Minister Mangena and Hans IttmannFirst, there was dancing and singing by a choir and drums which set the African mood. Then Elise del Rosario gave a terrific welcome, talking about the promise of Africa and the role operations research plays in achieving that promise. This was followed by a welcome by the Minister for Science and Techology, Mosibudi Mangena. Minister Mangena is one of us: he has a masters degree in applied math, and he gave a talk that suggested he understood operations research. As a colleague said, the talk also suggested a speech writer familiar with the Science of Better web site. The minister took the opportunity to tweak Hans Ittmann, Organizing Chair for the conference, for not offering enough operations research to his department. Hans promptly promised to work hard to embed OR throughout the South African government. Could people even 15 years ago imagine a South Africa where an esteemed black Cabinet Minister would tease a (white) operations research professor about the role operations research plays in the government? I will write later about how I feel holding a conference in South Africa at this time, but I loved the exchange.

One person who gets credit in South Africa for the amazing transformation over the last two decades was the opening speaker Clem Sunter. Clem is a Brit who has been in Africa for 35 years, working for the Anglo American Corporation and more recently heading up the Anglo American Chairman’s Fund, a corporate social responsibility fund.

Clem does “scenario planning” and has been described as Africa’s Alvin Toffler. In short, he is a futurist. In the 1980s, he developed two scenarios for South Africa. The “High Road” was a South Africa transformed by negotiation leading to political settlement (I do not need to remind people that South Africa in the 1980s was torn by the odious apartheid). The “Low Road” was confrontation leading to a wasteland. He talked about these scenarios to both FW de Klerk, leader of the National Party, and the imprisoned Nelson Mandela. Mandela and de Klerk shared the Nobel Prize for their combined work to end apartheid.

Clem opened his talk by suggesting scenario planning is like poetry, where operations research is like an essay. He uses possible futures to frame debates about where companies, countries, and societies are going. When speaking about South Africa, he clearly sees the problems: crime, HIV/AIDS, and a declining infrastructure for some. But he also understands the strengths: resources, tourism, and its role (like that of Dubai in the mid-east and Hong Kong in Asia) as a gateway to Africa. In his view, one key to success is the turnaround in Zimbabwe. He believes that President Mugabe is in an endgame, and once he is gone, tremendous investment will flow back into Zimbabwe, with much going through South Africa, and with much of the rebuilding being done by South Africans.

I must say I am not a great fan of futurists. They are either so vague they become like horoscopes in that you can read almost anything into what they say, or make so many “predictions” that almost any future will have been predicted by them. Clem seemed more thoughtful on the purpose of scenarios. He has scenarios not to predict the future but to frame the debate. It is in this approach that he sees poetry in scenario planning.

There was a terrific question right at the end of the talk (if anyone noted who asked the question, please let me know September 8 addition: asked by Jonathan Rosenhead of LSE) about the role of operations research in scenario planning. We do scenarios all the time: we create stochastic models of the future and simulation then provides us with scenarios that we can optimize over. How does this relate to Clem’s use of scenarios. He said that there was a large difference, whereby his scenarios change conversation while technical scenario building has not had the same broader impact. And, he said, there is a Nobel Prize in the waiting for someone who combines the two. You can find out more about Clem and his thoughts at a website for him and his colleague Chantell Ilbury

I enjoyed the talk a lot, and learned a lot about South Africa and the challenges the country faces. And I was a little inspired to think about how the things I do can change conversations. I am sure there are differing opinions, since this was not a typical OR talk.

Unusually for an operations research conference, not a single person (out of 500 or more) left the plenary once Clem began speaking. That is the sign of a successful opening plenary!

Up tomorrow, back to traditional OR with one of my favorite people in the field (and my co-advisor 20 years ago), Don Ratliff from Georgia Tech on Lean Supply Chains.