Month: April 2008

Citations in Management Science and Operations Research

The Tepper School, in its promotion and tenure cases, has had more conversation about (if not emphasis on) citation counts for papers. This is partially a “Google Scholar” effect: the easier it is to find some data, the more people will rely on that data. Those of us who bring notebook computers to the tenure cases can immediately add new “data” to the discussion. I fear I have been a big part of this trend here, using Google Scholar as a quick measure of “effect”. I have even written about this on the blog, in an effort to find highly cited OR papers. The software “Publish or Perish” by Harzing.com has been invaluable in this regard: it generates results from Google Scholar, collates them, combines likely double entries, and sorts them in a number of ways. Through them, I can learn immediately that my h index is 19 (not quite: it doesn’t combine some papers, so my h index is closer to 16), and that a paper Anuj Mehrotra and I wrote on graph coloring is my highest cited “regular” paper, and that paper is the third most cited paper ever in INFORMS Journal on Computing. I can even search the citations of my nemeses (“Hah! I knew that paper was never going to lead to anything!”). What a great way to spend an afternoon!

But does any of this mean anything? In the current (March-April 2008) issue of Interfaces, Malcolm Wright and J. Scott Armstrong take a close look at citations in an article entitled “Verification of Citations: Fawlty Towers of Knowledge?” (Interfaces, 38(2): 125-139). They talk about three types of errors (and I recognize the risks that this blog summary may end up committing some of these errors, including the count of errors! [In fact, the initial post of this entry misspelled the title.]):

  1. Failure to include relevant studies
  2. Incorrect references
  3. Quotation errors

Much of the article involves a paper written by Armstrong and Overton in 1977 on overcoming non-response bias in surveys. The overlap in authors means that the authors probably understand what the paper meant to say but the authors may have a certainly lack of objectivity on the subject. Despite the objectivity issue, the article makes for stunning reading.

The most persuasive of the arguments regards “Quotation Errors”. While it is not new to note that many authors don’t read all of the papers in their references, it is amusing to see how many people can’t even get the basic ideas right:

A&O is ideal for assessing the accuracy of how the findings were used because it provides clear operational advice on how to constructively employ the findings. We examined 50 papers that cited A&O, selecting a mix of highly cited and recently published papers. …

Of the articles in our sample, 46 mentioned differences between early and late respondents. This indicates some familiarity with the consequences of the interest hypothesis. However, only one mentioned expert judgment, only six mentioned extrapolation, and none mentioned consensus between techniques. In short, although there were over 100 authors and more than 100 reviewers, all the papers failed to adhere to the A&O procedures for estimating nonresponse bias. Only 12 percent of the papers mentioned extrapolation, which is the key element of A&O’s method for correcting nonresponse bias. Of these, only one specified extrapolating to a third wave to adjust for nonresponse bias.

The paper was also not referred to correctly in many cases:

We examined errors in the references of papers that cite A&O. To do this, we used the ISI Citation Index (in August 2006). We expected this index to underrepresent the actual error rate because the ISI data-entry operators may correct many minor errors. In addition, articles not recognized as being from ISI-cited journals do not have full bibliographic information recorded; therefore, they will also omit errors in the omitted information. Despite this, we found 36 variations of the A&O reference. Beyond the 963 correct citations, we found 80 additional references that collectively employed 35 incorrect references to A&O. Thus, the overall error rate was 7.7 percent.

Their discussion of “missing references” was not convincing to me (though it is unclear how to do this in an objective way). The authors did some google searches and checked how often some of their key ideas were missing. Since they found about a million results for “(mail OR postal) and survey” AND (results OR findings), and only 24,000 of those mention (error OR bias), of which only 348 mention Armstrong OR Overton, they conclude that their work on bias is not well represented in real surveys. It doesn’t take much experience with google search to believe that the baseline of a million pages does not correspond to one million surveys (and the vast majority of internet surveys have zero interest in accuracy to the level of A&O). Their work with Google Scholar had similar results, and I have similar concerns over the relevance of the baseline search. But I certainly believe this qualitatively: there are many papers that should provide more relevant references (particularly to my papers!).

The authors have a solution to the “quotation error” issue that is both simple and radical:

The problem of quotation errors has a simple solution: When an author uses prior research that is relevant to a finding, that author should make an attempt to contact the original authors to ensure that the citation is properly used. In addition, authors can seek information about relevant papers that they might have overlooked. Such a procedure might also lead researchers to read the papers that they cite. Editors could ask authors to verify that they have read the original papers and, where applicable, attempted to contact the authors. Authors should be required to confirm this prior to acceptance of their paper. This requires some cost, obviously; however, if scientists expect people to accept their findings, they should verify the information that they used. The key is that reasonable verification attempts have been made.
Despite the fact that compliance is a simple matter, usually requiring only minutes for the cited author to respond, Armstrong, who has used this procedure for many years, has found that some researchers refuse to respond when asked if their research was being properly cited; a few have even written back to say that they did not plan to respond. In general, however, most responded with useful suggestions and were grateful that care was taken to ensure proper citation.

Interesting proposal, and one most suitable for things like survey articles that attempt to cover a field. I am not sure how I would react to requests of this type: I suspect such requests might fall through the cracks amongst all the other things I am doing. But if the norms of the field were to change…

The article has a number of commentaries. I particularly liked the beginning of the Don Dillman article:

In 1978, I authored a book, Mail and Telephone Surveys: The Total Design Method (Dillman 1978). According to the ISI Citation Indexes, it has now been cited in the scientific literature approximately 4,000 times. When reviewing a summary of its citations, I discovered citations showing publication dates in 24 different years, including 1907 (once) and 1908 (three times). Citations erroneously listed it as having been published in all but three of the years between 1971 and 1995; there were 102 such citations. In addition, 10 citations showed it as having been published in 1999 or 2000. I attribute the latter two years to authors who intended to cite the second edition— although I had changed the title to Mail and Internet Surveys: The Tailored Design Method (Dillman 2000).

I discovered 29 different titles for the book, including mail descriptors such as main, mall, mial, mailed, and mailback. The telephone descriptor also had creative spellings; they included telephon, teleophone, telephones, telephone, and elephone. Not surprisingly, my name was also frequently misspelled as Dillon, Dilman, Dill, and probably others than I was unable to find. I also discovered that I had been given many new middle initials. A similar pattern of inaccuracies has also emerged with the second edition of the book.

I do believe that technology can help with some of these issues, particularly with incorrect references. But including relevant references and correctly summarizing or using cited references is an important part of the system, and it is clear that the current refereeing system is not handling this well.

Papers and commentary like this are one reason I wish Interfaces was available to the wider public ( I found an earlier version of the base article here, but no link to the commentaries), even if just for a short period.  The article and commentaries are worth searching around for.

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!