Month: May 2008

Open Access at Springer

Despite some philosophical/moral issues, I do a fair amount of work with commercial publishers. I just was co-Program Chair for the CPAIOR conference, and was delighted to publish the conference volume in Springers Lecture Notes in Computer Science series (despite the fact that LNCS has been dropped from the ISI indexing). I am considering starting a journal with Elsivier. Overall, while I prefer journals offered by professional societies (like INFORMS), I recognize the role commercial publishers play in supporting a field.

Still, I was taken aback by Springer‘s “attempt” at open access when I recently had a paper accepted in Annals of Operations Research. I had the option to make the paper open access. Here is what I was offered:

Upon publication, your article will be available to all subscribers of this journal. If that is what you want, click the button ‘No Open Access’ below. However, if you want your article to be available to everyone, wherever they are, whether they subscribe or not, then you should publish with Open Access. Springer operates a program called Open Choice that offers authors the option of having their articles published with Open Access in exchange for an article processing fee. The standard fee is US$3000. If you want to order Open Access, please click the button ‘Yes, I order Open Access’ below.

Fascinating, and somewhat appalling (though I might feel differently if I was paying in euros). I wonder if they ever get anyone to take that choice. I actually now feel worse about publishing with Springer: I would rather they simply take the position that publishing with them involves a transfer of copyright than to be offered such terms. It looks to me that this is just an attempt to provide an “open access” veneer rather than a serious attempt to face the intellectual property issues of commercial publishing.

Travel to South Africa

With the upcoming IFORS meeting in Sandton, South Africa, it was disheartening to see the recent violence in South Africa.  Of course, the violence against “foreigners” was not against tourists:  it was against Zimbabweans and other non-South Africans living in the townships.  Things seem to have calmed down, and here is one recent summary of the situation:

TravelHub (www.travelhub.co.za) – Xenophobia

THERE have been no further incidents of xenophobic violence reported since Sunday, May 25. South Africa is now in the process of dealing with the aftermath of the violence, notably the humanitarian crisis that has developed due to the thousands of displaced immigrants being housed in camps across the country. These people lack basic necessities such as food, blankets, toiletries and clothes. Recent reports confirm that violence between those displaced has broken out in some of these camps. Government is expected to announce its plan of action for dealing with the crisis later today (May 29).

The other major problem, which is affecting tourism, is the country’s image. Despite the calm of the last few days, countries are continuing to issue travel warnings for their citizens who plan to visit South Africa. No alerts have told travellers to avoid South Africa completely but a number of countries, including the United States, have issued warnings against travel to township areas. Yesterday Australians were told to avoid township tourism, and the general advice for visiting South Africa remained the same: exercise a high level of caution.

The Foreign and Commonwealth Office (FCO) issued a similar warning yesterday, advising travellers to avoid Gauteng townships.

The warnings acknowledge that tourists are not the targets of the recent violence, but point out that they might be caught up in surrounding violence, should it flare up again. This poses a major problem for companies involved in township tourism, who are trying to carry on business as usual and convince tourists that the townships are safe. Townships in the Eastern Cape, which had no reported incidents of xenophobic violence, Orlando West in Soweto and others that have been calm over recent weeks, should be safe to visit but it will take months, if not years, before the horrific images of the violence broadcast internationally will fade and tourists will again readily head to South Africa’s townships.

I am very much looking forward to both the conference and the side activities I have planned in South Africa.  I have even bought a new camera (DSLR: Canon EOS) with a big (300mm) lens for the safari part of my visit. I hope to see many of you there!

More success for OR and sports

ILOG has a press release on using constraint programming for the Japanese Football (soccer for Americans) League.  Seems like a pretty big league:

J. LEAGUE is a top professional football (soccer) league in Japan and one of the most successful leagues in the Asian Football Confederation. The organization recognized a need to automate and streamline its complex match scheduling process, involving 33 teams and 79 schedules, with a total of 682 matches over a 10-month playing season. With no packaged application available for complex scheduling, J. LEAGUE decided on a custom approach based on optimization technology from ILOG. Optimization improves business decision making speed and efficiency by allowing organizations to calculate the best utilization of existing resources — in this case, team personnel, stadiums and spectators.

It is not clear why 33 teams need 79 schedules!  I find it hard enough to find a schedule for every team in a league.

Some Final CPAIOR Thoughts

I have returned from Paris (my original plan was to go to Italy for IPCO, but I had to change that). Here are some thoughts from the CPAIOR conference:

  1. It is impossible to blog while being Program Chair, particularly in Europe (for me). Program Chair at the conference is the easiest job: the choices have all been made, so it is really a matter of sitting back and seeing how everything turned out. But I was nervous about the timing, since the schedule was more packed in that I had liked, so I sat near the front to provide pressure on speakers to keep to their time. Being in the front, I didn’t feel right tapping on my notebook, so I didn’t blog during the talks. But jetlag made me fall asleep anytime I was within fifty feet of a bed, so I couldn’t blog from my hotel room. Hence, just a few comments now!
  2. Pascal van Hentenryck gave a fascinating review of the history of constraint programming, based on an imaginary conversation with his advisor J.L. Lauriere describing what has happened to CP over the last 30 years (Lauriere died about 5 years ago). Lauriere wrote the pioneering paper in constraint programming back in 1978, centered around a language entitled ALICE. It was really neat to see how many of the ideas we have today are within that 1978 paper (though the 1978 paper and language structure is such that it is really hard to see how we got to where we got). I had not heard of Lauriere, but that is perhaps not so surprising: constraint programming is not my main home base, and Lauriere was perhaps best known within France. Correction added June 2.  Lauriere was on Pascal’s committe, but his adviser at the University of Namur was Baudouin Le Charlier.
  3. Francois Laburthe of Amadeus (a company like Sabre) gave the final plenary, and it complemented Cindy Barnhart’s very well. Francois talked about the business side of airline schedules: how do you show them to customers and determine the best routes for them. Companies like Orbitz and Expedia do this all the time, and I hadn’t realized how hard that it is to do. One stat of his I liked: pre-Internet, systems were designed to serve five price queries for every ticket sold. Now the number is closer to 1000. Given the number of searches I do before every trip, I can believe it!

Overall, I thought the conference went very well. Francois Fages, who was responsible for local organization among other things, chose a very nice boat on the Seine for dinner, and everything went very well in general.

In addition to Cindy Barnhart’s talk, I guess I most liked the workshop that Robin Lougee-Heimer put together on open-source solvers in CP and operations research. I was a little surprised that most open source constraint programming systems don’t do it for the community of developers. For the most part, they do it as a convenient license for distribution. Only COIN-OR really seems to be working to get a community of people working at improving code.

It was a great conference. Next year, it will be in Pittsburgh, where my colleagues John Hooker and Willem-Jan van Hoeve have to do all the work.

More about Airlines and Operations Research

Another sign of the difficulty operations research has in getting implemented within airlines comes from the National Post in Canada:

Attention passengers: most airlines make boarding more painful than necessary by insisting on traditional back-to-front boarding even though new research shows it can be done faster.

Back-to-front boarding is only marginally more efficient than front-to-back boarding, but much slower than filling seats in alternate rows, beginning with windows seats from back to front, then middle and aisle seats.

The new research, to be published in the forthcoming edition of the Journal of Air Transport Management, found this optimal boarding method cuts down boarding time by about half, from 25 minutes to 12 or 13 minutes for an aircraft that seats 120 passengers. Back-to-front boarding is “very likely the second worst method,” concludes American physicist Jason Steffen.

There has been previous work on improved boarding.  Will airlines use it?  Probably not:

In Canada, the two major airlines say they like the status quo and have no plans to redraft boarding policies based on new research showing there are faster ways.

WestJet has tried out different boarding methods, and has landed on random boarding. The company won’t release details of its tests, but says random boarding is up to 20% faster than sequential boarding.

Air Canada conducted its own research a few years ago to test various boarding techniques, including random boarding and window-middle-aisle ordering.

Spokesman Peter Fitzpatrick conceded that while traditional back-to-front “is not necessarily the most expeditious, we concluded it is the most customer-friendly. Customers are accustomed to the system, so we do not have to provide a lengthy explanation prior to every flight.”

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.

More on Operations Research in the Air

The New Yorker article by Malcolm Gladwell entitled “In the Air” had a second theme (I talked about the first theme: the multiple near-simultaneous discovery of inventions): the engineering of the sorts of insights that lead to invention. Can you create an environment where invention occurs?

The typical picture of an inventor is an obsessed loner wandering around until a lightening bolt strikes and the inventor puts it all together. Nathan Myhrvold, who made a fortune at Microsoft, thought that perhaps he could made invention and creativity happen. He did this by bringing together bunches of smart people, giving them broad topics, and seeing what resulted. And lots happened:

How useful is it to have a group of really smart people brainstorm for a day? When Myhrvold started out, his expectations were modest. Although he wanted insights like Alexander Graham Bell’s, Bell was clearly one in a million, a genius who went on to have ideas in an extraordinary number of areas—sound recording, flight, lasers, tetrahedral construction, and hydrofoil boats, to name a few. The telephone was his obsession. He approached it from a unique perspective, that of a speech therapist. He had put in years of preparation before that moment by the Grand River, and it was impossible to know what unconscious associations triggered his great insight. Invention has its own algorithm: genius, obsession, serendipity, and epiphany in some unknowable combination. How can you put that in a bottle?

But then, in August of 2003, I.V. held its first invention session, and it was a revelation. “Afterward, Nathan kept saying, ‘There are so many inventions,’ ” Wood recalled. “He thought if we came up with a half-dozen good ideas it would be great, and we came up with somewhere between fifty and a hundred. I said to him, ‘But you had eight people in that room who are seasoned inventors. Weren’t you expecting a multiplier effect?’ And he said, ‘Yeah, but it was more than multiplicity.’ Not even Nathan had any idea of what it was going to be like.”

The original expectation was that I.V. [Intellectual Ventures, a company formed by Myhrvold] would file a hundred patents a year. Currently, it’s filing five hundred a year. It has a backlog of three thousand ideas. Wood said that he once attended a two-day invention session presided over by Jung, and after the first day the group went out to dinner. “So Edward took his people out, plus me,” Wood said. “And the eight of us sat down at a table and the attorney said, ‘Do you mind if I record the evening?’ And we all said no, of course not. We sat there. It was a long dinner. I thought we were lightly chewing the rag. But the next day the attorney comes up with eight single-spaced pages flagging thirty-six different inventions from dinner. Dinner.”

This is exactly the environment we would love to have in universities. Once in a while, when a group of faculty get together there is an environment of creativity and excitement. Most of the time, we whine about the administration.

Operations Research in the Air

My colleague Steve Spear has a posting on the “Against Monopoly” blog (not against the board game, but commentary on intellectual property issues) regarding a New Yorker article entitled “In the Air” by Malcolm Gladwell. Gladwell makes the point that many advances have been simultaneously made by multiple groups. From the discovery of dinosaur bones to the telephone to cancer treatments, there seems to be something in the air that gives the right time for a discovery. The New Yorker article gives a number of examples:

This phenomenon of simultaneous discovery—what science historians call “multiples”—turns out to be extremely common. One of the first comprehensive lists of multiples was put together by William Ogburn and Dorothy Thomas, in 1922, and they found a hundred and forty-eight major scientific discoveries that fit the multiple pattern. Newton and Leibniz both discovered calculus. Charles Darwin and Alfred Russel Wallace both discovered evolution. Three mathematicians “invented” decimal fractions. Oxygen was discovered by Joseph Priestley, in Wiltshire, in 1774, and by Carl Wilhelm Scheele, in Uppsala, a year earlier. Color photography was invented at the same time by Charles Cros and by Louis Ducos du Hauron, in France. Logarithms were invented by John Napier and Henry Briggs in Britain, and by Joost Bürgi in Switzerland.

“There were four independent discoveries of sunspots, all in 1611; namely, by Galileo in Italy, Scheiner in Germany, Fabricius in Holland and Harriott in England,” Ogburn and Thomas note, and they continue:

The law of the conservation of energy, so significant in science and philosophy, was formulated four times independently in 1847, by Joule, Thomson, Colding and Helmholz. They had been anticipated by Robert Mayer in 1842. There seem to have been at least six different inventors of the thermometer and no less than nine claimants of the invention of the telescope. Typewriting machines were invented simultaneously in England and in America by several individuals in these countries. The steamboat is claimed as the “exclusive” discovery of Fulton, Jouffroy, Rumsey, Stevens and Symmington.

We see this in our own field when multiple groups seem to solve longstanding open problems almost simultaneously, often years after the problem was formulated. Such happenings inevitably lead to accusations and recriminations, with cries of plagiarism and other nefarious goings-on. Of course, ideas are stolen and the stress of publication can lead to short-cuts, and these are rightly decried, but I think there is something to this “in the air” phenomenon. Many simultaneous discoveries may be just that: simultaneous discoveries.

The Against Monopoly blog points out that these simultaneous “inventions” are often the outcome of a tremendous amount of public buildup. The “invention” is then just a small step, with a corresponding willingness to fight a patent battle. As the blog says:

I certainly came away from the article believing even more strongly in the Boldrin-Levine [see here] contention that intellectual property rights just aren’t necessary when you have the shoulders of giants to stand on.

In operations research, we saw this with our most famous patent issue: AT&T’s patent for “Karmarkar’s Algorithm” for linear programming. I remember the INFORMS (ORSA/TIMS at the time) conference when this came out. Researchers were canceling their talks on the simplex algorithm, since it no longer seemed relevant. Doctoral students were ruing their choices, and giving up hope for a successful academic career since they had bet on the wrong horse. Of course, the algorithm had no such effect. Research on effective implementations of the simplex algorithm was spurred by the competition, and research on interior point algorithms moved quickly to respond. The field has been greatly enhanced by having competing techniques. The patent didn’t help this advance, and was not financially successful for AT&T (I do not believe), but Karmarkar’s algorithm was a beginning not an end.

But it wasn’t even a beginning. “Karmarkar’s” algorithm was actually a well-known nonlinear programming algorithm in disguise, with its roots dating to the 60s (Karmarkar announced “his” algorithm in 1984). This equivalence to known work doesn’t take away from what Karmarkar did. Believing that an approach more suitable for nonlinear programming would be efficient and effective for linear programming was a big step. And it made a huge difference on the field. But, in keeping with Stigler’s Law (no invention is truly named after its inventor), Karmarkar’s algorithm could really take on many other names.

Change in attire

Since today was

  1. The first working day after classes ended last week, and
  2. Warm and sunny in Pittsburgh,

I went to work in shorts and sandals. In honor of this, I would like to direct your attention to an article in Inside Higher Ed by Erik M. Jensen entitled “A Call for Professional Attire“. In the article, Jensen notes the standard sartorial choices of professors:

Professors, it’s been said, are the worst-dressed middle-class occupational group in America.

He offers a Uniform Uniform Code:

Faculty members shall, when on college grounds or on college business, dress in a way that would not embarrass their mothers, unless their mothers are under age 50 and are therefore likely to be immune to embarrassment from scruffy dressing, in which case faculty members shall dress in a way that would not embarrass my mother.

A response by the economist Brad Delong brings out how dress needs to change depending on the audience:

With math-oriented students, however, a tie tells them that I spend too little time thinking about isomorphisms.

For the record, when I teach MBAs, I teach the first class in a suit and tie. The second class, I take off the jacket half-way through. The third class, I take off the jacket immediately. The jacket is never to be seen again: I trust my students assume I take it off in my office, though it never leaves my closet. Later in the course, I might lose the tie for a couple of lectures if the course is going well; If the course is going poorly, I put on “power ties” of increasing power until I get the course going well again. When doing video teaching, I used to wear shorts with a shirt and tie, but the new system in place shows all of me, so I am back to wearing big-boy pants for all my classes. I only change the structure of my facial hair in the middle of a course if it is going so poorly that I need to subtly get across the idea of “new beginnings”. And I often wear shorts and am otherwise an embarrassment to my mother outside of teaching days.

Business Intelligence and Operations Research

In the past couple of years, a field called “business intelligence” has sprung up. Based on the premise that businesses should get more out of data, business intelligence mixes data mining, algorithms, visualization and other approaches to help businesses make better decisions.

Of course, I thought that was the definition of operations research! Ever since I came across the area, I have included some of the blogs in my blogroll (see, for instance, James Taylor’s Decision Management and Smart (Enough) Systems). I find this area interesting, but I never can quite get my brain around what they are trying to say. It is like they are taking an area I know very well and translating it into a different language which I kind-of understand, but not quite well enough to grasp what they are saying.

Intelligent Enterprise (part of the group that publishes Information Week) has a short article “What BI Practitioners Can Learn from Operations Research”. It begins with the Netherlands Railway Edelman story, then continues to express confusion on the lack of interaction of the two fields:

It would be natural for BI practitioners to embrace OR, which has long focused on automating decision making, surely the goal of those who talk about closed-loop BI. “OR starts with the decision and works back to figuring out what math and data will help with devising a better solution, while BI tends to start with the data and see what can be done with it,” says James Taylor, co-author of Smart (Enough) Systems and one who believes that OR and BI are complementary but quite different. “OR folks tend to be focused on the nitty-gritty of day-to-day operations, and they use data from operational systems. BI tends to be focused on knowledge workers, data warehouses, and aggregation.”

It would be natural for the OR community to reach out to the BI world and its community of business-focused knowledge workers, who are increasingly looking to build out their analytical toolkits. “C-level decision makers are turning to analytics for help in the decision-making process,” writes Peter Horner, editor of Analytics, a new magazine published by the Institute for Operations Research and the Management Sciences (INFORMS). “When you see terms like operations research (OR), think analytics.” Many in the BI world, who are already supporting those executive decision makers, are saying close to the same things about BI and analytics.

Given the close kinship of BI and OR, one wonders why these two camps have long existed as separate communities?

SAS’s Mary Crissy (who I still think of as Major Crissy, though she left the military some years ago), has what I think is a pretty good explanation:

“Operations researchers don’t interact with the IT community as much as they ought to,” says Mary Crissey, an analytics marketing manager at SAS, a council officer of INFORMS, and, apparently, one of the few vendor executives with a foot in both the BI and OR camps.

“Academic mathematicians are not worried about what terms are buzzing about in the business world,” Crissey says. “They talk to each other in their mathematical language of equations and theory without getting entangled in terminology such as BI. Pure Intelligence for business or public service organizations all boils down to data analysis; they just don’t call it BI.”

Having gone through fights over “operations research”, “management science”, “decision engineering”, “analytical decision making” and countless others over the 50+ years of existence, the field is not particularly excited about embracing a new name for our field.

I guess I see BI’s relationship with OR to be similar to operations management’s relationship with our field. OM uses OR an awful lot, and OM would not be successful as a field without OR. But OM is not a subfield of OR: sometimes it uses approaches that are outside the range of OR (including organizational theory, case studies, or other methods). That is great! OM people are trying to solve problems, and they should be using whatever methods seem appropriate. Similarly, BI uses (or should use) OR extensively. And OR people should see the BI community as a great source of problems and inspiration (and should make an effort to learn their language). But BI will inevitably use non-OR methods for some of their issues, so is rightly not “the same as” OR. But we as a field should know more about what they are doing if we are going to be part of this business direction.