Knuth and Multicore Systems

Donald Knuth has been publishing “fascicles” from his Volume 4 (Combinatorial Algorithms) of his epic The Art of Computer Programming. These are shortish (100-150 page) sub-chapters of a work on an area that expands faster than Don can write. You can download some of the preliminary versions on Knuth’s page to get the flavor.

Knuth was interviewed by Andrew Binstock of InformIT. Great interview with very provocative questions and answers! I particularly liked the exchange on parallel algorithms and multicore systems. Don is not a fan:

Andrew: One of the emerging problems for developers, especially client-side developers, is changing their thinking to write programs in terms of threads. This concern, driven by the advent of inexpensive multicore PCs, surely will require that many algorithms be recast for multithreading, or at least to be thread-safe. So far, much of the work you’ve published for Volume 4 of The Art of Computer Programming (TAOCP) doesn’t seem to touch on this dimension. Do you expect to enter into problems of concurrency and parallel programming in upcoming work, especially since it would seem to be a natural fit with the combinatorial topics you’re currently working on?

Donald: The field of combinatorial algorithms is so vast that I’ll be lucky to pack its sequential aspects into three or four physical volumes, and I don’t think the sequential methods are ever going to be unimportant. Conversely, the half-life of parallel techniques is very short, because hardware changes rapidly and each new machine needs a somewhat different approach. So I decided long ago to stick to what I know best. Other people understand parallel machines much better than I do; programmers should listen to them, not me, for guidance on how to deal with simultaneity.

Andrew: Vendors of multicore processors have expressed frustration at the difficulty of moving developers to this model. As a former professor, what thoughts do you have on this transition and how to make it happen? Is it a question of proper tools, such as better native support for concurrency in languages, or of execution frameworks? Or are there other solutions?

Donald: I don’t want to duck your question entirely. I might as well flame a bit about my personal unhappiness with the current trend toward multicore architecture. To me, it looks more or less like the hardware designers have run out of ideas, and that they’re trying to pass the blame for the future demise of Moore’s Law to the software writers by giving us machines that work faster only on a few key benchmarks!

I have been struggling to take advantage of my (now not so-)new computer and its 8 cores. Since about 90% of my used CPU cycles are done in CPLEX, and I only have a single-core license, I am actually running at about 10% capacity on that machine. And my efforts to write some specialized codes have not been successful, though that is perhaps more due to lack of time and effort than any inherent difficulty. Does the new generation of OR researchers understand and feel comfortable with multi-core programming? Or are we now just going to stall in terms of computation speed in practice?

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.

OR Forum on SWOT for Operations Research

There is a new paper in the OR Forum area of the journal Operations Research. Written by ManMohan Sodhi and Chris Tang, it is entitled “The OR/MS Ecosystem: Strengths, Weaknesses, Opportunities, and Threats” and analyzes the state of the field, with a particular emphasis on the relationship between academia and practice. Check out the paper and commentaries, and provide your own thoughts on the issues! I am the Area Editor of the OR Forum: you can read more about what the area is about in this posting.

One bittersweet aspect: Mike Rothkopf provided a commentary one week before his death. I wish he could be here to add to the conversation (on this and many other things).

ROADEF Challenge

The French OR society ROADEF runs a challenge every two years. This year’s challenge (actually the 2009 challenge) is on an interesting and important topic: flight disruption.

—————————————————————–
Subject of the challenge 2009: Disruption Management for commercial aviation
—————————————————————–
Commercial airlines operate flights according to a published flight schedule that is optimized from a revenue standpoint. However, external events such as mechanical failures, personnel strikes, or inclement weather frequently occur, disrupting planned airline operations. In such cases, it is necessary to find efficient solutions that minimize the duration of the disruption, thus minimizing its impact.

Traditionally, resources are re-allocated sequentially, according to a natural hierarchy: aircraft, crew, passengers. Nonetheless, this method is seriously flawed. Namely, decision making at the local level, concerning one resource, can lead to global repercussions, affecting all resources. For example, a change in the flight schedule, potentially impacting aircraft resources, may also lead to a missed connection for crew or for passengers. Thus, an increasing effort is being made to integrate different levels of decision making. The topic proposed for this challenge follows this trend, since it aims at re-assigning aircraft and passengers simultaneously in case of disruptions.

There are already some instances at the challenge web site to get you started.

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.

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.

Netherlands Railway Edelman summary

I just got out of the “reprise” of the winning Edelman prize work by Netherlands Railways, and it was very, very good.

If you have been to the Netherlands, they have a very nice way of handling their trains:  every route repeats every hour.  So if you want to go from Utrecht to Amsterdam, there are trains at 13, 25, 43 and 55 minutes after the hour, every hour.  Of course, the size of the train changes depending on the expected demand.

The Dutch have had the same schedule since 1970, but it was time for a change.  Demand has doubled in that period, and there was little opportunity to increase the infrastructure.  So could a better schedule reduce costs and improve service?  Of course, or it wouldn’t be an Edelman Prize winner!

There were three pieces to the system:  the timetabler, the crew assignment system, and the rolling stock assignment system.  The timetabler was very interesting.  You can formulate the problem as a mixed-integer program, but the cyclic nature of the hourly schedule requires the use of “mod” constraints.  They tried MIP for a while (and even called in the big gun Lex Schrijver to look at it:  I saw a talk by Lex a decade or more ago on work he did with Netherlands Railway on purchasing rail cars that is still one of the nicest applications talks I have ever seen), but eventually went over to constraint programming.  From the talk, it appears they used constraint programming primarily to find a feasible solution, and then did some local improvements, but I will have to wait for the paper to be sure what is being done.

The other problems were solved with specialized integer programming methods.

The best part of the talk was their discussion of the implementation, which is where the models really came through.  The plan was to have an important length of track doubled to coincide with the new schedule.  That doubling didn’t happen, so they had to reschedule the crew essentially at the last minute.

The results have been really impressive.  Crew costs are down 4% and rolling stock usage is down 6%, combining for an annual benefit of $75 million.  As is not uncommon in OR projects, the system is both cheaper and works better.  Punctuality is at an all-time high, and customer satisfaction is similarly improved.  The increase in punctuality allowed them to increase fares by an additional 2%, for further profits of $30 million.  Other than the fare increase, this looks like win-win:  better service, more convenient times, cheaper operating costs.

At the end there was a nice video clip of the Minister of Transport saying how important OR is.

A worthy Edelman winner!

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.