The End of the INFORMS Practice Conference …

and the start of the INFORMS Conference on Business Analytics and Operations Research.

The INFORMS Practice Conference has long been one of my favorite conferences.  In addition to the inspirational Edelman Competition presentations, the organizers do a great job of identifying presenters for a range of industries, illustrating the wide applicability of operations research.  The conference is on a much more manageable scale than the INFORMS Annual Meeting (or EURO meetings) and is typically held in an interesting location.

The INFORMS blog  has just announced that the name for this conference series will change to the INFORMS Conference on Business Analytics and Operations Research.  Business analytics is a term that has gained a lot of recognition recently (we recently added a track to our MBA program called “business analytics”).  INFORMS has a pretty good definition of the term:

Business analytics facilitates realization of business objectives through reporting of data to analyze trends, creating predictive models for forecasting and optimizing business processes for enhanced performance.

While all of those aspects are “operations research” it is that last phrase “optimizing business processes” that really links business analytics to the OR/MS world. Previous approaches like “business intelligence” did not really integrate aspects of optimizing business processes.  But with this definition “business analytics” really is “operations research” and vice-versa.

I have struggled with the adoption of the phrase “business analytics”.  INFORMS (and its founding organizations ORSA and TIMS) has had innumerable discussions on what our field should be named and even now INFORMS embeds two alternatives: Operations Research and Management Science, the ORMS of INFORMS.  Do we need another name?  And there are aspects of “business analytics” that seem to me to be a stretch to call operations research:  once you start tossing in dashboards and scorecards and the rest of the buzzwords, I start racing back to my safe world of cutting planes and submodular functions.  But it is all about using data and models to make better decisions.  And if the market likes “business analytics” then I’m good with it.

I worry about the longevity of the term.  Will this term last or in five years will it feel like “e-business” does today?  It does strike me as a term that has the chance of being around for a while, particularly if it is embraced by organizations like INFORMS.

One big problem for the phrase:  there is no good phrase to identify those that do it.  “Business analysts” is not right:  analyst comes from analysis, not analytics.  “Business analytickers?”  I think not.  On the other hand, “operations research” has that problem too.  “Operations researchers” just doesn’t sound right.

So I am good with the title.  However, can we call it the “INFORMS Conference on Business Analytics and Operations Research”, its official name, not the “INFORMS Analytics Conference” as given in the INFORMS blog title?  Including the “operations research” name is going to be important to the branding of this conference.  At least as far as us ORers are concerned.

Exciting Times for the INFORMS Meeting

Lots of great things are being planned for the upcoming INFORMS Meeting. Let me highlight two.

First, there is a wonderful series of panel discussions planned (if I say so myself:  I organized this particular track).  The idea is to explore issues of professional interest (rather than technical tracks, which are interesting in their own right but not what we were aiming for here).   I previously asked for advice and feedback on topics, and ended up finding some great panel organizers.  Here is the list we ended up with:

Sunday Nov 07, 08:00 – 09:30 : Panel Discussion: Social Networking and Operations Research
Chair: Laura McLay
Sunday Nov 07, 13:30 – 15:00 : Panel Discussion: OR in Engineering Schools
Chair: Mark Daskin
Monday Nov 08, 08:00 – 09:30 : Panel Discussion: INFORMS Journals
Chair: Terry Harrison
Tuesday Nov 09, 08:00 – 09:30 : Joint Session Invited Panels /JFIG: Success as a Junior Faculty
Chair: Burcu Keskin
Tuesday Nov 09, 11:00 – 12:30 : Panel Discussion: Operations Research/Management Science in Business Schools
Chair: Jeff Camm
Tuesday Nov 09, 13:30 – 15:00 : Panel Discussion: Academic Administration and Operations Research/ Management Science: A Good Combination?
Chair: Cynthia Barnhart
Tuesday Nov 09, 16:30 – 18:00 : Panel Discussion: Skills and Career Paths in Industry
Chair: Ranganath Nuggehalli

I think there is nice variety in the topics.  I am particularly looking forward to the session on social networks.   Laura McLay, Aurelie Thiele, Anna Nagurney, and Wayne Winston will discuss how twitter, facebook, blogs and so on can be used in the operations research world.  Sounds like a great way to start of the conference.  I’ll definitely be there live tweeting/blogging.

The second big activity I am looking forward to is “Forrest-Fest”.  I am a big fan of COIN-OR, the open source initiative in operations research (for a few more weeks, I sit on its Strategic Leadership Board).  John Forrest was one of the key people in the founding of COIN, and continues to play an extremely active role in code development and debugging.  John is “retiring” from IBM;  COIN-OR is turning 10 years old.  The combination is obvious!  It is time for a famous COIN-OR Party!  You can check out their extensive set of talks at their wiki.  The COIN-OR reception is always enjoyable, and is promised to be “thoroughly optimized”.  I do worry the shape of people Monday morning:  robustness constraints are often ignored during the Sunday reception.

Between the program and the city of Austin, I am very much looking forward to the conference.  I hope to see many of you there!

INFORMS Optimization Awards

The INFORMS Optimization Society just announced their 2010 awards.

I [Nick Sahinidis, President of the Society] am delighted to announce the winners of the 2010 INFORMS Optimization Society Prizes:
George L. Nemhauser, winner of the first Khachiyan Prize for his life-time achievements in the field of optimization
Zhi-Quan (Tom) Luo, winner of the 2010 Farkas Prize for his outstanding contributions to the field of optimization
Anthony Man-Cho So, winner of the 2010 Prize for Young Researchers for his paper “Moment inequalities for sums of random matrices and their applications to optimization,” Mathematical Programming, DOI: 10.1007/s10107-009-0330-5
Shiqian Ma, winner of the 2010 Student Paper Prize for his paper “Fast multiple splitting algorithms for convex optimization,” co-authored with Don Goldfarb.

A very impressive group!  I have worked with Nemhauser, and he and I are co-owners of a small sports scheduling firm.  I’d like to think sports scheduling helped a little bit in getting this award, but since our most cited paper together is only his 14th most cited paper (it is my 5th most cited, both stats according to Google scholar), I guess he is really getting it for his work on more fundamental issues in integer programming (and other areas!).

Congrats to all the winners.  You can find out more about their work, and even see them all together at the upcoming INFORMS meeting:

The detailed award citations for this year’s prizes can be found at http://optimization.society.informs.org/prizes.html.  The four prize winners will present their work at a special session at the INFORMS meeting in Austin, scheduled for November 7th from 13:30 to 15:00 and entitled “Optimization Society Prizes.”

A New Approach to MaxFlow?

The MIT public relations office is reporting a new result on the maximum flow problem.  It appears that work by Kelner, Madry, Christiano, Spielman and Teng (in some permutation:  not surprisingly, the MIT release stresses the MIT authors) has reduced the complexity of maxflow to (V+E)^4/3 (from (V+E)^3/2.  Details are pretty sketchy, but the approach seems to use matrix operations instead of the more combinatorial “push flow along this path (or edge)”.  From the announcement:

Traditionally, Kelner explains, algorithms for calculating max flow would consider one path through the graph at a time. If it had unused capacity, the algorithm would simply send more stuff over it and see what happened. Improvements in the algorithms’ efficiency came from cleverer and cleverer ways of selecting the order in which the paths were explored.
But Kelner, CSAIL grad student Aleksander Madry, math undergrad Paul Christiano, and Professors Daniel Spielman and Shanghua Teng of, respectively, Yale and USC, have taken a fundamentally new approach to the problem. They represent the graph as a matrix, which is math-speak for a big grid of numbers. Each node in the graph is assigned one row and one column of the matrix; the number where a row and a column intersect represents the amount of stuff that may be transferred between two nodes.

In the branch of mathematics known as linear algebra, a row of a matrix can also be interpreted as a mathematical equation, and the tools of linear algebra enable the simultaneous solution of all the equations embodied by all of a matrix’s rows. By repeatedly modifying the numbers in the matrix and re-solving the equations, the researchers effectively evaluate the whole graph at once.

I am a little hesitant here, since I can’t find the relevant paper.  Worse, the presentation abstract talks about approximate maximum flow (see the September 28 entry at the MIT seminar listing), which would then add in some extra terms for exact max flow.   So I welcome more information on the result.

In any case, it is exciting to see a new approach to these sorts of problems.  If past experience is any guide, if this approach is workable, we can expect to see an avalanche of papers applying the approach to all sorts of network flow problems: shortest path, min cost flow, generalized networks (with multipliers) and so on.  A likely good place to start is this overview paper by Spielman.

Call for Challenging MIP Problems

MIPLIB is a collection of instances of Mixed Integer Programs.  Versions of MIPLIB have been around since 1992, and these have been invaluable as we see how we have advanced in solving difficult MIP instances. Some instances that were essentially unsolvable twenty years ago can now be solved in a fraction of a second.  We know we are getting better!  Of course, there is a downside:  maybe we are just getting better at solving MIPLIB instances.  For instance, here is an extract from an excellent optimization code to attack MIPLIB:

if (problem == "team10") then {
       sol_val = 924;
    }
else if (problem == "a1c1s1") then { ...

Now, I don’t claim that any real code cheats this blatantly, but it is inevitable that as codes use benchmarks like MIPLIB, they will become tuned to the issues that come from those instances.

This makes it important that MIPLIB reflect a broad range of issues faced “in the real world”.  So it is very good that the MIPLIB people (a group based at ZIB in Berlin, but including people from all over) are updating the library to create MIPLIB 2010.  If you have hard or real-life MIP instances, particularly if they are taking 15 minutes to 2 hours with commercial codes, you are welcome to upload those instances for consideration for the new library.  The more varied the library, the better our field will be.

There is one other biasing aspect that an update to MIPLIB 2010 does not fix and that is the emphasis on talking about integer programs as MPS files.  Once an instance is in an MPS file, it is often extremely difficult to back out the underlying structure.  Our constraint programming brethren are happy to talk about formulations with global constraints like alldifferent and to have codes that explicitly take advantage of those structures. I do wonder if we would be better at solving integer programs if we talked about them as higher-level structures (like tour(x1,x2,x3) and matching(x,y) and other common substructures).  By limiting ourselves to MPS format, the structures we exploit tend to be those easiest to find, like knapsack and setcovering).

But that is a topic for the future:  right now, we need to be sure MIPLIB 2010 is as varied and interesting as it can be!

Definitive Word on P!=NP Paper

Lance Fortnow of the blog Computational Complexity has, I believe, the definitive word on the P!=NP paper by Deolalikar (saying in a sentence what I couldn’t quite manage in two pages):

Proving P  ≠ NP will require pure genius but you shouldn’t need a Fields medalist to verify the proof.

Secondary message:  a good way to determine if a proof will work is to count the “clearly”s and “should be able to”s:  more than one or two and the proof likely will fall apart at the slightest breath.

Reading “Numbers Rule” by Szpiro

It is Labor Day weekend here in the US, so, in addition to the mandatory grilling and bicycling with Alexander, I have some time to laze about on the porch reading books (and drinking beer, which is also legally required in my jurisdiction).  I have been reading Numbers Rule by George Szpiro.  This is a fascinating book on the history of thought about voting rules, starting back with Plato and continuing with Pliny the Younger, Llull, Cusanus, Borda, Condorcet, Laplace, Dodgson, and ending with the impossibility results of  Arrow, Gibbard, and Satterthwaite.  Interleaved are a few chapters on the problem of allocating seats in a parliament.

I have done work in this area (and Bartholdi, Tovey and Trick even make an appearance on page 115) but I don’t consider myself a specialist.  Even specialists, however, might learn something on the history of the field from this book.  The Llull-Casanus period (roughly 1200 A.D. to 1450 A.D.) in particular was new to me.  This pre-Renaissance period was not one that generally generated a lot of deep insights into non-religious issues (in the Western world), but voting was one area that was of great interest to the ecclesiasticals, most notably in the election of the Pope, but also in electing people for lesser positions such as abbot.

Voting seems to be an easy problem:  we do it all the time.  “How many people want A?  How many people want B?  OK, A wins” is certainly used in our three-person household.  But voting is much harder when there are more than two possible outcomes.  With A, B, and C as possibilities, having each elector vote for one and then taking the one with the most votes (plurality elections) leads to all sorts of bad outcomes.  For instance, it is arguable that having Nader in the 2000 election with Bush and Gore (in the U.S. Presidential election) led to Bush winning while without Nader, Gore would have won.  This is an example of violation of “Independence of Irrelevant Alternatives”:  shouldn’t an election result be consistent whether or not a third (or fourth or fifth) candidate enters?  In other words, if A beats B when only the two run, if C also runs then it should be that either C wins or A continues to win.  Stands to reason! But plurality voting is terrible with respect to this condition, so “splitting the opposition” is a standard way to strategically manipulate such an election.

The book makes it clear that issues of fairness in elections with more than two candidates go back to Greek times.  There have been two main approaches in getting beyond plurality voting.   In both cases, electors rank all of the candidates (unlike in plurality where only the most-preferred candidate is listed).  In the first method, candidates get points based on their placements.  For a 4 candidate election, every “first place” vote is worth 4, every second place vote is 3, and so on.  The candidate with the most votes wins.  In the second approach, the pairwise matchups are analyzed and the person who would win the most pairwise elections is deemed the overall winner.  Ideally, there is a candidate who would win against any other candidate in a pairwise election, and that person is a natural choice for winner (and a choice that plurality is not guaranteed to choose).  Such a candidate is known as a Condorcet winner.

I had always credited the foundation of these two approaches to Borda and Condorcet respectively.  Both lived in the 1700s in France, Borda being a mathematician and military officer, Condorcet being a “pure” scientist and government official.  But the real credit for these approaches should really go to Casanus and Llull four hundred years earlier.  Numbers Rule gives a very good description of their work and all that was new to me.

One aspect of Numbers Rule that I really like is the brief biographical summary at the end of every chapter. Every chapter is based on one (or a few) key figures.  Rather than try to weave the biography of that person in with the description of their findings in voting, only the key features are in the main text, while the biographical summary provides a deft summary of the rest of their lives.  The people came alive through those summaries, but extraneous details did not hinder the main exposition.

The book is non-mathematical, in the that the very few equations are exiled to chapter appendices, but it is analytical in the sense that concepts are clearly and completely described.  There is no hand-waving or “This is neat but really too hard for you”.  Even NP-Completeness gets covered in a reasonable manner (in the context of my own work).

It is only in the coverage of my own work that I really disagree with the author.  Briefly, Charles Dodgson (better known as Lewis Carroll of Alice in Wonderland fame) proposed that the winner of an election should be the one who becomes the Condorcet winner with the fewest number of changes to the electors’ ballots.  Bartholdi, Tovey and I proved that determining the Dodgson winner is NP-Hard.  Szpiro writes that this result was the “death knell” of Dodgson’s Rule, which I think vastly overstates the case.  We solve NP-Hard problems all the time, through integer programming, constraint programming, dynamic programming, and practically any other -programming you like.  There are very, very few practical elections for which we could not determine the winner of the election in a reasonable amount of time (exceptions would be those with a vast number of candidates).  In my mind, the main problem with NP-Hard voting rules is that the losers cannot be succinctly convinced that they really lost.  Without a co-NP characterization, losers have to be content with “The computer program I wrote says you lost”, which is unlikely to be satisfying.  But I don’t think Dodgson’s rule is dead and I certainly don’t think I killed it!

Operations research comes out very well in the book.  In addition to accurately describing Bartholdi, Tovey and me as Professors of Operations Research (kinda accurately:  I was a doctoral student when the paper was written but an Assistant Professor at CMU when it was published), OR takes a star turn on page 189 when the work of Michel Balinski is described.  Here is part of the description:

One of Balinski’s areas of expertise was integer programming, a branch of operations research.  Developed before, during and after World War II, operations research originated in the military where logistics, storage, scheduling and optimization were prime considerations.  But it soon acquired enormous importance in many other fields, for example in engineering, economics and business management.  While game theory, developed at the same time, was mainly of theoretical interest, operations research was immediately applied to practical problems.  Whenever something needed to be maximized or minimized – optimized for short – and resources were constrained, operations research offered the tools to do so.

What a lovely paragraph!

If you have any interest in learning about why voting and apportionment are not straightforward, and want a readable, history-oriented book on approaches to these problems, I highly recommend Numbers Rule:  reading it has been a great way to spend a lazy weekend.

The List Every University Should Want to Be On

About this time last year, I asked advice about where a high school senior should consider for college engineering.  At the back of my mind, I was figuring that this is a pretty smart kid and both of his parents have PhDs, so finding a place that might get him fired up enough to consider education beyond the bachelor’s degree would be a good idea.  But what places really have an environment that inspires students to go on to still-higher education?  While I had thought a smaller school would be a good choice, I also bought into the argument that students are inspired by top-notch research around them, arguing for a larger research-oriented institution.

The NSF has done a study on this, and is listing the undergraduate programs whose students are most likely to go on to get a PhD in a science or engineering field.  Thanks to Laura McLay for pointing to this article on the subject.  Here is the table that lists the top 50 schools in terms of fraction of students who go on to get a science and engineering doctorate:

The results are pretty stunning for a lot of reasons:

  1. The list is dominated by private schools, with only three public schools in the top 50.
  2. About half the schools are “Research – Very High”, denoting the most active research institutions (there are three levels of research activity in the Carnegie Classification), with the other half being small undergraduate-oriented colleges.
  3. The effect is significant, with a factor of seven difference between number 1 and number 50 on the list.  The average “Research – High” university has a value of 1.5 (1.5% go on to doctorates), so the lift for number 50 is more than 3, while that for Cal Tech is 23 (a graduate of Cal Tech is 23 times more likely to go on for a science and engineering doctorate than a graduate of an average research university).
  4. Berkeley (who also has the largest number of graduates with PhDs) is the only large public university on the list.  No Michigan (who has the second third largest number of graduates with PhDs) , Georgia Tech, or other large public university is to be seen.

Now this sort of study has limitations.  In retrospect, it is not surprising that a school that graduates lots of, say, accountants will naturally have a lower fraction who go on to get doctorates.   Most big public universities have honors programs or other structures to nurture those with further educational aspirations, and I am sure that the results for those in these specialized programs look like the results for the schools in the table above.

But if you want to be surrounded by those likely to go on to get doctorates in science and engineering, you should either go to one of the very top private research schools or go to a small private liberal arts college.  Carnegie Mellon or Oberlin (or, particularly, Cal Tech), that is the question!

P versus NP and the Research Process

By now, everyone in computer science and operations research is aware of the purported P<>NP proof of Vinay Deolalikar of HP Labs.  After intense discussion (mainly through blogs and wikis), the original paper was taken down, and Vinay has prepared a new version for submission.  He claims:

I have fixed all the issues that were raised about the preliminary version in a revised manuscript (126 pages); clarified some concepts; and obtained simpler proofs of several claims. This revised manuscript has been sent to a small number of researchers.  I will send the manuscript to journal review this week. Once I hear back from the journal as part of due process, I will put up the final version on this website.

I am convinced by Dick Lipton’s blog entry and by Scott Aaronson’s commentary suggesting fundamental flaws in the paper, but since Vinay has not retracted the paper, I will look forward to the definitive version of the paper.  For a detailed description of the issues, press coverage, and other aspects, polymath has an extensive wiki on the topic.

What I find most intriguing is the field’s response to this claimed proof.  Proofs that P=NP or P<>NP are certainly not uncommon.  Gerhard Woeginger faithfully keeps track of these claims and is up to 62 in his list.  Some of these results come out of the operations research world.  For instance, Moustapha Diaby is a faculty member at the business school at the University of Connecticut and believes he has found linear programming formulations for NP-hard problems (number 17 on Woeginger’s list).

The Deolalikar paper is unique, however, in that many, many top mathematicians looked very closely at the paper and worked very hard to determine its correctness.  This group includes people like Fields-medal winner Terrence Tao and Polya and Fulkerson prize winner Gil Kalai.  Why did so many very smart people (and successful!  They don’t do wikipedia pages on just anyone [yet]) spend time on this while practically no one spends time with the other 61 purported proofs?

The most obvious reason is that this paper presented a fundamentally new approach to this problem.  As Lipton says: “the author has advanced serious and refreshingly new ideas of definite value”.  In this proof, Deolalikar uses finite model theory, an area of logic, to deduce structures in random satisfiability problems.  If P=NP, then the structures would have to be different than what is already known about random satisfiability problems in the critical region (this synopsis is vague to the point of not being usable). This is definitely a different direction than past efforts, bringing together a number of disparate fields.

Further, Deolalikar knows very well that there are a number of proofs in the literature that say “P<> NP cannot be proved this way”.  For instance, any result that cannot distinguish between the easy 2-satisfiability and the hard 3-satisfiability is doomed to failure (Aaronson’s blog entry gives a few others along with other signs to check for in claimed proofs). Deolalikar presented reasons for believing that his approach evaded the barriers.    This leads to excitement!  Could this approach avoid known invalid approaches?

Contrast this with papers that suggest that a linear programming model can correctly formulate an NP-complete problem.  Yannakakis showed that no symmetric formulation can do so, and that provides a powerful barrier to linear programming formulations.  Not only must a a formulation not be symmetric, but its asymmetry must be of the sort that continues to evade Yannakakis’ proof.  Without a strong argument on why an LP formulation fundamentally avoids Yannakakis’ argument, it is not even worthwhile spending time with LP formulations of  NP-complete problems.

This overwhelming doubt was clearly not felt by some referees who allowed Diaby’s papers to be published in “International Journal of Operational Research”, lending credence to the idea that the refereeing and journal process in operations research is broken (in my view, of course).  For the steps given in the Computational Complexity blog, we have have to add a step: “Your paper is accepted by a third tier journal and still no one believes it.”  Similarly, it will not be enough for me to see that Deolalikar’s paper is published:  at this point I trust the blogs (some of them, anyway) more than the journals!

Even if the Deolalikar result is shown not to be valid, the paper gives me enormous hope that someday the P<>NP (as I believe it is, rather than P=NP) will be proved.  We appear to be developing methods that will have some traction in the area.



Five Sundays, Mondays, and Tuesdays and Operations Research Training

A half dozen times in the past couple of weeks I have either been told, received an email, or otherwise ran across the following “fact”:

August 2010 has five Sundays, Mondays, and Tuesdays, and this won’t happen again for 823 years!

Wow!  That is pretty amazing.

It is also completely ridiculous and false.  May, 2011, for instance, has five Sundays, Mondays, and Tuesdays.  Even if the issue is an “August” with this structure, this occurs again in 2021 and 2027.  A moment’s thought reveals that you get five of those days anytime a month with 31 days starts on a Sunday, which has to be about 1/7 of them.   Since 7/12 of the months have 31 days, you would really expect about one month a year to have this structure, and that seems to be the case.

But, given all the repeats of this, there clearly are a lot of people who will buy into this sort of nonsense.  Why is that?  This really is a failure of mathematical training.  One reason we teach mathematics is to get people to think clearly and analytically on issues.  Ideally this would mean that people would immediately have an intuition that a result like this means that 31 day months (or August in particular) rarely start on a Sunday.  But experience shows that is not the case:  if the first day of some months is rarely a Sunday, surely I would have noticed that by now!  A quick check of any online calendar shows that the “fact” is false, and somebody has invented something ridiculous in order to see how many people can fall for this false meme.

Perhaps in operations research we have an advantage:  we are used to questioning the assumptions that go into models and looking carefully at the resulting solutions.  “Is this really linear?”  “If I assume X, what does that imply about Y?” “Does this answer make sense?”  Perhaps with a bit more OR training, urban myths will have to become a bit more sophisticated before they grab the public’s attention.