Michael Trick’s Operations Research Blog

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.

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!

2008 Edelman Prize

Just a quick note that the 2008 Edelman Prize was won by Netherlands Railways. That was not one that I saw today, so I’ll check out their presentation tomorrow and report on it. Congrats to the winners! This is a very competitive prize, and INFORMS does a great job in providing a classy awards ceremony for it at the Practice Meeting.

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 Vazakopoulos 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.

ILOG Optimization Decision Manager Hands On

I sat through (OK, half of) the ILOG workshop on their Optimization Decision Manager.  The ILOG ODM can be seen as a front-end to the rest of the ILOG Optimization systems (like OPL).  I would think of it as a super-sized way of doing version control and what-if analysis.  I use ILOG software in a lot of my research (and consulting) and I generally do something like

1. Optimize a system
2. Change some of the constraints and data
3. Not like the results, and
4. What was 1. again?

Rather than do intermediate saves (hmmm… I wonder what “testjunk.mod” is?), ODM allows you to save scenarios with differing data, models, parameters, goals and so on and then compare data and results between models.  This makes it much easier to mess around with instances and keep track of what works and what doesn’t work.   Embedded within in ODM is the opportunity to make constraints “soft” (putting them in the objective, with differing weights) and to do goal programming.

I am not quite certain the goal user for this.  I like the idea of using this in my own work, where I am the user.  I shudder about giving this system to someone without some reasonable understanding of operations research:  the “end user” here had better be pretty sophisticated.

Overall, I am glad that I attended the half of the session I did.  I do think we need better hardware/software/display for demos:  squinting at what appeared to be 4 point font at a screen was not particularly illuminating, and the resulting headache chased me from the room halfway through.

Bixby, Gu, and Rothberg leave ILOG

I arrived at the INFORMS Practice Meeting, and one of the first people I met was Bob Bixby. I had heard some rumors, and noticed that the affiliation on his badge was Rice University, so I was eager to chat with him. I wrote about Bixby last year when he was the IFORS Distinguished Lecturer at the EURO Conference. I think Bixby has been the most influential person in our field over the last fifteen years or so, and that influence has been primarily through a computer code he created. Though he began his career as a top-notch combinatorial mathematician, he decided at one point to write the world’s best linear programming code. This code, called CPLEX, has had a tremendous influence on the practice of operations research, greatly expanding our field’s reach and influence. Bixby’s company was eventually bought by ILOG, a company that also does constraint programming and business rules systems (see Simon Holloway’s view of ILOG from someone versed in business rules), and ILOG has consistently improved CPLEX and provided support for the team developing it. Bixby has had a number of roles within ILOG, including Chief Science Officer.

Bixby, along with two on the CPLEX team, Ed Rothberg and Zonghao Gu, have left CPLEX in the last few months. This puts the IP/LP software world in a tremendous state of flux. On the positive side, three of the best people in our field will be able to spread their skills to other companies (Bob was cagey on where he is thinking about going, and I have not talked to Rothberg or Gu). On the negative side, there are now questions about two (with the Fair Isaac purchase of Dash Optimization) of the top codes that underly much of linear/integer programming based research and practice. Of course, CPLEX has a large (15 person perhaps) development team, and no one is irreplaceable, but that is a lot of change in a short period.

8:50 PM Correction. Ed Rothberg was not on the CPLEX team when he left ILOG. Further corrections as conditions warrant!

9:40 Addition.  Just so the following is not buried in the comments, here is the response from Irv Lustig from ILOG:

Further corrections to Mike’s post:

Bob Bixby has not been working on CPLEX for 4 or 5 years. Ed Rothberg has not been working on CPLEX for 2 years. Both of them had been working on ILOG’s FPO product. So only Gu has left the CPLEX R&D team.

As mentioned by Mike, ILOG acquired CPLEX over 10 years ago, and it is quite unusual in the software industry for a founder of an acquired company to remain more than 4 years after the acquisition. We were fortunate that Bob stayed for the 10+ years that he did.

I was also one of the original CPLEX developers, and I have not touched the code in over 10 years, moving on to other roles within ILOG. It is a testament to CPLEX and ILOG that we have replaced Bob, Ed and myself with new developers, and we have recently hired very good talent to improve the CPLEX product. The CPLEX product will survive just fine after these departures of our friends and colleagues.

Off to INFORMS Practice

After a quick sidetrip to Chicago, I’m off to the INFORMS Practice Meeting in Baltimore.  I’ll try to do some live (or almost live) blogging from the event.  If you are there and see me, be sure to say hi!