Category: Conferences

Cindy Barnhart at CPAIOR

I am in Paris attending the CPAIOR (Constraint Programming/Artificial Intelligence/Operations Research) conference. I was the co-Program chair for this, which means my work is done, but now I get to see how good the papers we accepted are. On the whole, things are very good, with a surprise or two (each way!).

Cindy Barnhart of MIT was the plenary speaker this morning, talking about challenges and opportunities for OR in the airline industry, with an emphasis on plane and crew scheduling. Cindy has been working on airline applications for 20 years, so she has a wealth of experience to bring to this. She began with her view on what aspects of mathematical modeling are most useful in this application area. In her view, two key aspects are

  • Composite variables: defining variables to include complicated structures. For instance, instead of just having a variable for the number of planes on a particular leg to meet demand, the variable would be choices of combinations of planes, with the variable being 1 if that combination is used. While this leads to more variables, the resulting models are much easier to solve, since their linear relaxations are closer to being integer.
  • Implicit formulations: Instead of including all levels of variables, include only the highest level variable, but add constraints so that there is a feasible assignment for the other variables. For instance, instead of including all individual planes, only have a variable for the number of planes of a particular type. Add some constraints so that once the number of planes is known, individual planes can be feasibly assigned.

This lead to the question, then, “Why are things so bad”? Why is on-time service down, and why are people so angry at airlines (particularly in the US)? It is clear that planned schedules don’t correspond to actual. How can models help to close that gap? Cindy offered a wealth of models and insights:

  1. Creating robust schedules. The key idea in this model is to give more slack to planes more likely to be delayed. Surprisingly, even without changing the schedule, it is possible to reduce delays simply by the assignment of planes to legs: in essence, make sure planes coming in from San Francisco (where delays due to fog are common) are assigned outgoing legs a little later than an identically arriving plane from Phoenix. These delays can be reduced quite a bit more by slightly (up to 15 minutes) modifying the schedule.
  2. Auctioning for landing slots. Surprisingly in the US, at almost all airports there is no coordination among airlines in their schedules, so far too many planes arrive or leave in a short period, overwhelming the airport capacity. It seems obvious that slots should be auctioned off so that airport capacity is not violated.
  3. Dynamic Scheduling. Predicting demand on any particular leg on a particular day is clearly one that is approximate at best. As demand comes in, it is possible to change the capacity between cities by, for instance, changing a flight so that a formally illegal connection is now legal. Of course, this must be one-way: all previously purchased connections must remain legal. An airline could even “refleet” a flight, by changing the plane to a larger one or a smaller one to meet demand (in this case, the airline crew must still be legal for the flight, and these changes propagate through the system as the “wrong” planes continue through). Even minor changes (no more than a 15 minute move) can increase the profitability of a schedule by 2-4%, with most of the gain through schedule changes, not refleeting.
  4. Passenger-Centered recovery. In case of a “disruption” (a storm or other issue), airlines face the problem of getting planes, crews, and passengers back to normal as quickly as possible. Normally airlines treat the problem in that order: get the planes in the right place, then get the crews, then worry about the passengers. What if airlines combine all three and try to minimize average customer disruption while getting planes and crews back on schedule? It is possible to greatly reduce the average passenger delay but the airlines might have to delay a plane that is ready to go. So the delay of “undisrupted” customers will go up a bit in order to greatly reduce the delay for “disrupted” customers. That is going to be a hard step for an airline to do.

Nice talk, but it made me think that airlines are harder to work with than the groups I normally work with.

Internet and Operations Research

MIT is holding a conference on Operations Research and the Internet at the end of May, and it looks excellent! They have some very smart people, like David Williamson of Cornell and Meredith Goldsmith of Google, speaking and their topics look very much like strong operations research: no fluff! Here is Williamson’s abstract to give a flavor for the conference:

An Adaptive Algorithm for Selecting Profitable Keywords for Search-Based Advertising ServicesIncreases in online search activities have spurred the growth of search-based advertising services offered by search engines. These services enable companies to promote their products to consumers based on their search queries. In most search-based advertising services, a company selects a set of keywords, determines a bid price for each keyword, and designates an ad associated with each selected keyword. When a consumer searches for one of the selected keywords, search engines then display the ads associated with the highest bids for that keyword on the search result page. A company whose ad is displayed pays the search engine only when the consumer clicks on the ad. With millions of available keywords and a highly uncertain clickthru rate associated with the ad for each keyword, identifying the most effective set of keywords and determining corresponding bid prices becomes challenging for companies wishing to promote their goods and services via search-based advertising.

Motivated by these challenges, we formulate a model of keyword selection in search-based advertising services. We develop an algorithm that adaptively identifies the set of keywords to bid on based on historical performance. The algorithm prioritizes keywords based on a prefix ordering — sorting of keywords in a descending order of profit-to-cost ratio. We show that the average expected profit generated by the algorithm converges to near-optimal profits. Furthermore, the convergence rate is independent of the number of keywords and scales gracefully with the problem’s parameters. Extensive numerical simulations show that our algorithm outperforms existing methods, increasing profits by about 7%. We also explore extensions to current search-based advertising services and indicate how to adapt our algorithm to these settings.

This is joint work with Paat Rusmevichientong (Cornell).

Looks like a very good conference.

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.

INFORMS Prize 2008

The INFORMS Prize is given to an organization for “effective integration of operations research into organizational decision making”.  It is given to organizations for sustained use of operations research.  The criteria are

  1. Variety of Applications of OR
  2. Competitive Advantage to the Organization
  3. Business Impact
  4. Business  Model for Success
  5. Endorsements (from top-level management)
  6. Overall Quality of the Application

INFORMS just announced at the INFORMS Practice Conference the 2008 winner to be GE Global Research, Risk and Value Management Laboratory, with Intel and MITRE as the honorable mentions.  The CTO of GE gave a very nice speech about the role OR plays at GE.

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:

  1. Insight
  2. Importance
  3. Simplicity
  4. Robustness
  5. Breakthrough
  6. 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:

  1. 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.
  2. If you dare to make better things, you will push against the status quo and need courage in your convictions
  3. 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.

Get your registration in for the INFORMS Practice Meeting

I really like the INFORMS Practice Meeting.  It is much different than the regular INFORMS conference.  The key difference is that not everyone speaks.  At regular INFORMS (or EURO or IFORS), practically everyone there will give a 20-25 minute talk on their own research.  At the Practice Meeting, speakers are carefully selected in order to present the best practical work, along with the most important methodological advances (generally in the form of tutorials).  As an example of the talks, here is the “Supply Chain” track:

  • Procter & Gamble – William Tarlton, Supply Chain R&D Manager, Personal Beauty Care Products, on implementing inventory optimization at P&G.
  • Pepsi Bottling Group – Arzum Akkas, Senior Project Manager, Supply Chain Technology, on retail out-of-stock reduction in a direct store delivery environment .
  • Pennsylvania State University –Terry Harrison, Professor of Business, Professor of Supply Chain & Information Systems, and Thomas Robbins, Instructor in Supply Chain & Information Systems, on services supply chain.
  • Xilinx – Alex Brown, Principal Engineer and Supply Chain Architect, on collecting and using demand information from customers and distributors to improve forecasts and supply chain performance.
  • IBM  –Markus Ettl, Manager of Supply Chain Analytics & Architecture, IBM Research, and Blair Binney, Manager of Demand/Supply Planning Process Transformation, IBM Integrated Supply Chain, on how analytics and collaborative processes improve distributor and IBM performance in the supply chain.
  • University of North Carolina – Brian Tomlin, Assistant Professor of Operations, Technology and Innovation Management, on supply chain risk management.

This is a great mix of academics and business executives, and I guarantee that the speakers will have spent significant time honing their presentations.

Of course, the conference is pretty pricey, but if you are doing (or considering doing) OR in practice, or if you teach courses on the practical use of OR, this is a must see conference.  The hotel deadline is in a couple of days.

I’ll be there, and perhaps do a bit of live blogging along the way.

Edelman Finalists Announced

The finalists for the 2008 Franz Edelman Award for Achievement in Operations Research and the Management Sciences have been announced. The Edelman Awards are a big thing in OR. The prize is given to the best use of operations research in practice. Even getting to be a finalist is a lot of work: this is not just a matter of submitting a paper and seeing how it goes. The finalists have to work even harder. They need to prepare a highly professional presentation, with the best presentations getting the support of a firm’s very top management (one year, the South African defense department was a finalist, and President Mandela provided a letter of support). Each finalists is assigned a coach to help them prepare their presentation (the late Rick Rosenthal was proud of the role he played as a coach, and I think finalists working with him may have had a bit of an advantage). And the projects have to be real, not hypothetical. Without verifiable and significant effect, a project cannot be a finalist, let alone a winner.

INFORMS has jazzed up the competition quite a bit in the last years, with fancy presentations at the Practice Meeting. I think this is great: these projects save, often, hundreds of millions of dollars, or improve many lives. They deserve a celebration.

This year’s finalists are an interesting bunch:

1. Federal Aviation Administration, for a project entitled “Airspace Flow Programs,” which gives the FAA greater ability to control the nation’s skies at times of peak consumer usage and flight congestion.

2. Netherlands Railways, for “The New Dutch Timetable: The O.R. Revolution,” a solution that improved on-time performance and capacity for more than a million daily train passengers.

3. StatoilHydro, one of the world’s largest gas producers, and Gassco, the independent Norwegian network operator, for “Optimizing the Offshore Pipeline System for Natural Gas in the North Sea.”

4. The City of Stockholm, Sweden for “Operations Research (O.R.) Improves Quality and Efficiency in Social Care and Home Help,” a program that has brought improvements to the complex scheduling of more than 4,000 providers who help the sick and the elderly.

5. U.S. Environmental Protection Agency, for “Reducing Security Risks in American Drinking Water Systems.”

6. Xerox, for “LDP Lean Document Production® – Dramatic Productivity Improvements for the Printing Industry,” which has bettered production and reduced costs for print shops and document manufacturers. The total impact to date on Xerox profits from the utilization of the LDP is about $200M. Xerox has filed 48 patents on this methodology and so far 11 have issued.

That’s three international organizations and only one traditional manufacturing finalist. The Swedish finalist in particular represents a strong trend in OR: using OR in the service sector.

I am looking forward to seeing the presentations at the Practice Meeting.

Call for Short Papers, CP-AI-OR 2008

I am co-program chair for CP-AI-OR 2008 to be held in May in Paris.  This year, we decided to allow “short papers” primarily to encourage presentation of preliminary work or work that might have appeared in another outlet but would still be of interest to the CP-AI/OR community.  If you aren’t familiar with CP-AI/OR, it is a small (roughly 100 person) conference that brings together people in constraint programming and operations research to discuss issues in common in the two field (I actually put constraint programming as part of operations research, but most constraint programmers don’t agree with me).

The deadline for short papers is February 15.  You can check out more details at the conference web site.