Category: OR in the Press

P=NP in the New York Times

The New York Times has a nice article on the recent Communications of the ACM article on P=NP (article at author Lance Fortnow’s site). I had read Fortnow’s article last month, and really liked it. In fact, I am surprised I didn’t blog it: I guess I was too busy worrying about false proofs of P=NP (or not).

The Times article does a good job of summarizing the problem in a non-technical way:

The challenge, in its simplest, but not most understandable phrasing, is to determine whether or not P equals NP. P stands for the class of problems that can be solved in polynomial time, or reasonably quickly. NP stands for the class of problems that can be verified in polynomial time — quickly. If it can be shown that P=NP, then it is possible that the world will be a very different place.

The main thrust of the New York Times article is simply how popular the paper is:

The editors of the journal said they were tickled to have a hit article on their hands.

”I don’t think we’ve ever had an article that started off with this kind of a bang,” said Moshe Y. Vardi, a Rice University computer scientist who is editor in chief of the journal. ”Our e-mail blast went out and thousands of people felt they had to click.”

The author of the article, Lance Fortnow, a computer scientist at Northwestern University McCormick School of Engineering, initially told Dr. Vardi that the article would be a short one. ”Still open,” he writes, was in first reaction to writing about the state of the work on solving the problem.

But the article does point to one possible new direction for attacking the problem:

There remains a glimmer of hope, he noted. An esoteric branch of mathematics known as algebraic geometry may offer an avenue to prove or disprove the problem, which was first outlined by Stephen A. Cook, a University of Toronto computer scientist, in 1971.

That prospect feels a bit intimidating. As Dr. Vardi said, “It’s a bit scary because we have to start learning a very difficult mathematical field.”

The Times did a good job on this one. Readable and accurate: good work John Markoff! And thanks Ted for the pointer.

Note added As a reddit commentator noted, “algebraic geometry” is hardly “an esoteric branch of mathematics”, so perhaps there is room for improvement in the article.

Operations Research is Taking Over the World

I often have postings that so-and-so from the world of operations research has become a dean or a provost or even a university president. Somewhat more rarely, I can talk about an operations researcher as a baseball player. Operations Research can lead to lots of jobs.

hatoyamaIt can even lead to becoming Prime Minister of the country with the world’s second largest economy. Yukio Hatoyama, Prime Minister designate for Japan, is not just trained in operations research but has a Ph.D. from Stanford in the subject. A search at google scholar suggests that his work was in the area of stochastic models in reliability, though it appears that his academic career was cut short (the google scholar counts suggest fairly … limited interest in his academic work). From an article in the Telegraph (UK):

Yet although Hatoyama refers jokingly to high office as “the family business”, he originally sought to avoid political life. After graduating from Tokyo University he completed an engineering PhD at Stanford University, and was set for an academic career in the US. However, his time in America coincided with the nation’s bicentenary, in 1976, and the presidential election that saw Gerald Ford replaced by Jimmy Carter. For the impressionable 29 year-old, it was an astonishing experience: such changes of government simply didn’t happen in Japan, where, despite political and monetary scandals, his grandfather’s party had remained in power since 1955.

The AP article has a nice one line definition of operations research:

Hatoyama knows the U.S. well, having obtained three postgraduate degrees from Stanford, including a doctorate in operations research, which consists of using mathematical and scientific models to make decisions within organizations.

Congratulations, Dr. Hatoyama! Now show the world how operations research training can be translated into political and economic leadership.

Data Mining and the Stock Market

As I have mentioned a number of times, I teach data mining to the MBA students here at the Tepper School.  It is a popular course, with something like 60% of our students taking it before graduating.   I offer an operations research view of data mining:  here are the algorithms, here are the assumptions, here are the limits.  We talk about how to present results and how to clean up data.  While I talk about limits, I know that the students get enthusiastic due to the not-insignificant successes of data mining.

We give students access to a real data mining system (SAS’s Enterprise Miner currently, though we have used SPSS’s Clementine Miner (now PASW, for some reason) in the past).  Invariably, students start putting in financial data in an attempt to “beat the stock market”.  In class, I talk about how appealing an approach this is, and how unlikely it is to work.  But students try anyway.

The Intelligent Investor column of the Wall Street Journal has a nice article on this (thanks Jainik for the pointer!) with the title: “Data Mining Isn’t a Good Bet for Stock-Market Predictions”.

The Super Bowl market indicator holds that stocks will do well after a team from the old National Football League wins the Super Bowl. The Pittsburgh Steelers, an original NFL team, won this year, and the market is up as well. Unfortunately, the losing Arizona Cardinals also are an old NFL team.

The “Sell in May and go away” rule advises investors to get out of the market after April and get back in after October. With the market up 17% since April 30, that rule isn’t looking so good at this point.

Meanwhile, dozens — probably hundreds — of Web sites hawk “proprietary trading tools” and analytical “models” based on factors with cryptic names like McMillan oscillators or floors and ceilings.

There is no end to such rules. But there isn’t much sense to most of them either. An entertaining new book, “Nerds on Wall Street,” by the veteran quantitative money manager David Leinweber, dissects the shoddy thinking that underlies most of these techniques.

The article then gives a great example of how you can “predict” the US stock market by looking at Bangledeshi butter production.  Now, I don’t buy the starkly negative phrasing of the column:  he (Jason Zweig) refers to data mining as a “sham”, which I think goes much too far.  Later in the article, he talks about what it takes to do data mining right:

That points to the first rule for keeping yourself from falling into a data mine: The results have to make sense. Correlation isn’t causation, so there needs to be a logical reason why a particular factor should predict market returns. No matter how appealing the numbers may look, if the cause isn’t plausible, the returns probably won’t last.

The second rule is to break the data into pieces. Divide the measurement period into thirds, for example, to see whether the strategy did well only part of the time. Ask to see the results only for stocks whose names begin with A through J, or R through Z, to see whether the claims hold up when you hold back some of the data.Next, ask what the results would look like once trading costs, management fees and applicable taxes are subtracted.

Finally, wait. Hypothetical results usually crumple after they collide with the real-world costs of investing. “If a strategy’s worthwhile,” Mr. Leinweber says, “then it’ll still be worthwhile in six months or a year.”

This is all good advice, and part of what I try to talk about in the course (though having the article makes things much easier).  My conclusion:  there is “sham” data mining, but that doesn’t mean all data mining is a sham.  I’d love to read the book, but the Kindle version is running at $23.73, a price that I suspect was set by data mining.

Three City Traveling Salesman Problem Solved by Bacteria!

A Guardian (London) article has the provocative title “Bacteria make computers look like pocket calculators” (thanks Hamish for the pointer). They report on how bacteria can be used to search through feasible solutions to the traveling salesman problem to find optimal solutions:

The research, published today in the Journal of Biological Engineering, proves that bacteria can be used to solve a puzzle known as the Hamiltonian Path Problem. Imagine you want to tour the 10 biggest cities in the UK, starting in London (number 1) and finishing in Bristol (number 10). The solution to the Hamiltonian Path Problem is the the shortest possible route you can take.

This simple problem is surprisingly difficult to solve. There are over 3.5 million possible routes to choose from, and a regular computer must try them out one at a time to find the shortest. Alternatively, a computer made from millions of bacteria can look at every route simultaneously. The biological world also has other advantages. As time goes by, a bacterial computer will actually increase in power as the bacteria reproduce.

Programming such a computer is no easy task, however. The researchers coded a simplified version of the problem, using just three cities, by modifying the DNA of Escherichia coli bacteria. The cities were represented by a combination of genes causing the bacteria to glow red or green, and the possible routes between the cities were explored by the random shuffling of DNA. Bacteria producing the correct answer glowed both colours, turning them yellow.

Where to begin? Does that article really talk about the 3-city TSP?

The belief that NP-completeness means that you have to search through every possibility fundamentally misunderstands fifty years of research in computational combinatorial optimization. The “three city” TSP was solved essentially as soon as it was defined. Even the 10 city TSP was solved long before people wanted to look through 3.5 million choices.

Even given the premise that bacteria can look through all possibilities, where does that leave us? Computationally, I really think that 300 cities is a good lower bound for exact work on the TSP (see Concorde, and the discussion given in a previous post). If someone has a bacterial technique that might work on 10 cities, how will it work on a system with 10^600 times the number of solutions? Will you have 10^600 bacteria? For those confused by orders of magnitude, the human body has about 10^14 cells (perhaps) and the universe has perhaps 10^80 atoms. I am glad that Bill Cook and his coauthors did not need to find 10^520 other universes to work with when solving 300 city TSPS, let alone the number needed for solving the 85,900 city problem they have solved (about 10^869527 possible tours).

Now, maybe the Guardian is not the best place to look for scientific detail. Going to the original paper, however, does not make one very confident:

The serial approach that most silicon computer algorithms use is not well suited for
solving NP-complete problems because the number of potential solutions that must be evaluated
grows combinatorially with the size of the problem. For example, a Hamiltonian Path Problem
for a directed graph on ten nodes may require as many as 10! = 3,628,800 directed paths to be
evaluated. A static number of computer processors would require time proportional to this
number to solve the problem. Doubling the number of nodes to 20 would increase the possible
number of directed paths to 20! = 2.43 x 10^18, increasing the computational time by 12 orders of
magnitude. Improvement in computational capability could come from parallel processing and
an increase in the number of processors working on a problem. Significant breakthroughs in this
regard may be possible with the development of biological computing, because the number of
processors grows through cell division.

OK, biologists, tell us about 10^600 parallelism. The “serial approach that most silicon computer algorithms use is not well suited for solving NP-complete problems” handles 300 cities pretty easily.

Don’t get me wrong. I think it is really cool that bacteria can solve traveling salesman problems. I think it would be equally cool if you could put together a Lego system that can solve 10 city traveling salesman problems. I have an issue, though, when the researchers believe they are really saying anything about solving NP-hard problems. Talk about relaxations and heuristic solutions, and then I am fascinated. Talk about comparisons to complete enumeration, and I have much less interest.

Contrary to the Guardian title, I think computers are still looking like computers, and biological systems have a long way to go to compete with calculators, at least as far as the TSP goes.

Pittsburgh: Hotbed of Operations Research and Baseball

Pittsburgh is becoming the center of the universe when it comes to combining baseball with operations research.  First, there is … well, me! … a Professor of Operations Research whose company provides Major League Baseball with their player and umpire schedules.  And, beginning last year, Pittsburgh has had Ross Ohlendorf, who has converted his Princeton degree in Operations Research and Financial Engineering into 5 wins and a 4.82 ERA (this year) as a starting pitcher for the Pittsburgh Pirates.

Ross seems a serious OR guy.  He did his undergraduate thesis on the financial return of players from the draft.  Overall, his conclusion was that teams get a pretty good return from the money they put into top draft picks.  ESPN has a nice article on Ross’s OR side.

In his thesis, Ross looked at drafts from 1989-1993.  Some players offered tremendous return:

Ohlendorf determined that the average signing bonus during those years was $210,236, and the average return was $2,468,127. Here are the top 10 players from his study.

Year of draft Pick # Name Drafting team Net return on investment
1992 58 Jason Giambi Athletics $33,795,272
1993 46 Scott Rolen Phillies $23,921,774
1993 14 Derrek Lee Padres $23,830,781
1992 1 Phil Nevin Astros $22,916,550
1990 20 Mike Mussina Orioles $21,679,781
1993 1 Alex Rodriguez Mariners $21,158,696
1992 19 Shannon Stewart Blue Jays $20,031,316
1991 13 Manny Ramirez Indians $19,757,230
1990 1 Chipper Jones Braves $18,438,782
1992 23 Jason Kendall Pirates $16,660,788

“So based on the assumptions I made in my paper, the A’s signing Giambi was the biggest winner in top-100 picks of the 1989 through 1993 drafts because he played extremely well in his first six years of major league service,” Ohlendorf said. “The White Sox did the best job in these drafts, with an internal rate of return of 217 percent. Their best signing was Frank Thomas.”

It is nice to see that Ross’s intelligence does not come at the expense of collegiality:

Ohlendorf is also a popular guy in the Pirates’ clubhouse. “He is so smart,” said Pirates shortstop Jack Wilson. “We give him a hard time about how smart he is, and he’ll come right back at us. We’ll say, ‘Ross, what is the percentage chance of this or that happening?’ and he’ll say, ‘The percentage chance of you winning that game of Pluck [a card game] is 65.678 percent, not 65.667 percent.”’

Starting pitcher might not be a standard job with an OR degree, but with a 2009 salary of $491,000, Ross may have found one of the more lucrative outcomes.

Ross:  if you read this, I’ll be the guy in the stands with a sign “Operations Researchers for Ohlendorf”!

Punk Rock OR Blogger Addresses Aviation Security

Laura McLay, author of Punk Rock Operations Research, has an interesting research paper out on identifying risky airline passengers in order to increase security for them. It is costly (both in money and in passenger inconvenience) to subject everyone to the highest level of screening. So who should be screened, given limited screening resources? Laura worked with Sheldon Jacobson (who is frequently seen in this blog) and Alexander G. Nikolaev on this problem, and they published their work in the June 2009 issue of IIE Transactions (IIE Transactions, Volume 41, Issue 6 June 2009 , pages 575 – 591).

From the VCU Press release:

Changes in aviation security policies and operations since the Sept. 11, 2001, terrorist attacks have resulted in every passenger being treated as a potential security risk, with uniform screening of passengers and their luggage. Screening all passengers the same way is costly and inconvenient for air travelers, according to the research, published in the June 2009 issue of “IIE Transactions.”

“We set out to find a real-time screening methodology that considers both available screening resources and the necessity of being robust in assessing threat levels,” said Laura A. McLay, Ph.D., an assistant professor in the VCU Department of Statistical Sciences & Operations Research. “This paper provides methodology to quickly determine which passengers are high-risk and who is low-risk and screen them accordingly,” McLay said.

Here is the full abstract:

Designing effective aviation security systems has become a problem of national concern. Since September 11th, 2001 passenger screening systems have become an important component in the design and operation of aviation security systems. This paper introduces the Sequential Stochastic Passenger Screening Problem (SSPSP), which allows passengers to be optimally assigned (in real-time) to aviation security resources. Passengers are classified as either selectees or non-selectees, with screening procedures in place for each such class. Passengers arrive sequentially, and a prescreening system determines each passenger’s perceived risk level, which becomes known upon check-in. The objective of SSPSP is to use the passengers’ perceived risk levels to determine the optimal policy for screening passengers that maximizes the expected number of true alarms, subject to capacity and assignment constraints. SSPSP is formulated as a Markov decision process, and an optimal policy is found using dynamic programming. Several structural properties of SSPSP are derived using its relationship to knapsack and sequential assignment problems. An illustrative example is provided, which indicates that a large proportion of high-risk passengers are classified as selectees.

As the New York Times reports, the TSA is upgrading its security by requiring things like real names (not nicknames) on tickets. Perhaps operations research can offset some of the inconvenience of these “upgrades”.

Brenda Dietrich “Most Creative”

Fast Company has IBM Vice President, Business Analytics and Mathematical Sciences, Brenda Dietrich as number 27 on their list of “100 Most Creative People in Business”.    Nice quote from her:

“Mathematics,” says Brenda L. Dietrich, 49, “is not mechanical. You’re finding how things look different on the surface and then seeing what they have in common underneath.”

It would be easy to put Brenda in the top 100 most brilliant or top 100 hardest working.  It takes creativity to put her as one of the 100 most creative, and it is a creativity I am delighted to see.  It can be hard to convince people that our field is primarily about creativity:  rather than paintbrushes, we use mathematics to be creative.

Thanks to the INFORMS e-news for the pointer.

Whither Data Mining?

The New York Times Magazine this week is a special issue on debt (a topic that has a particular resonance to me:  we are still paying off an expensive, but spectacular, year in New Zealand!).   There is a fascinating article on what credit card companies can learn about you based on your spending.   For instance,

A 2002 study of how customers of Canadian Tire were using the company’s credit cards found that 2,220 of 100,000 cardholders who used their credit cards in drinking places missed four payments within the next 12 months. By contrast, only 530 of the cardholders who used their credit cards at the dentist missed four payments within the next 12 months.

A factor of 4 is a pretty significant difference.  That should be enough to change the interest rate offered (and 2% default in 2002 is pretty high).   The illustrations to the article go on to suggest that chrome accessories for your car are a sign of much more likely default, while premium bird seed suggests likely on-time payment.

The article was not primarily about these issues:  it was about how companies learn about defaulters in order to connect to them so that they will be more likely to pay back (or will pay back more).  But the illustrations did get me thinking again about the ethics of data mining.  Is it “right” to penalize people for activities that don’t have a direct effect on their ability to payback but only a statistical correlation?  Similar issues came up earlier when American Express started to penalize people who  shopped at dollar stores.

I brought this up during my ethics talk in my data mining course, and my MBA students were split on this.  On one hand, companies discriminate on statistical correlations a lot:  teenage boys pay more for insurance than middle-aged women, for instance.  But it seems unfair to penalize people for simply choosing to purchase one item over another.  Isn’t that what capitalism is about?  But statistics don’t lie.  Or do they?  Do statistics from the past hold equivalent relevancy in today’s unusual economy?  Is relying on past statistics making today’s economy even worse?  Should a company search for something with a more direct correlation or is this correlation enough?

At the Tepper School at Carnegie Mellon, we generally put more faith in so-called structural models, rather than statistical models.   Can we get at the heart of what makes people default on credit card debt?  For instance, spending more than you earn seems one thing that might directly effect the ability to pay back debt.  It is hard to come up with a model where paying for drinks at the bar has a similar effect. But structural models tend to be pretty reduced-form.  It is hard to include 85,000 different items (like in the study reported by the New York Times) in such models.

I vacillate a lot about this issue.  Right now, I am feeling that data mining like the “spend in a bar implies default on credit cards” can lead to interesting insights and directions, but those insights would not be actionable without some more fundamental insight into behavior.  The level of “fundamentalness”  would depend on the application:  if I am simply deciding on a marketing campaign, I might not require too much insight;  if I am setting or reducing credit limits, I would require much more.

I guess this is particularly critical to me since I often play the bank at our Friday Beers.  Since we might have 20 people at Beers, the tab can reach $300, and I sometimes grab the cash from the table and pay by credit card.  Either the credit card companies have to come up with new rules (“If the tip is > 25% [as it often is with us:  they do like us at the bar!], then credit is OK; else ding the record”) or I better hit the ATM on Friday afternoons.

Much more on the NCAA Tournament

In the hyper-competitive world of operations research blogging, needing to teach a class can put you hopelessly behind.  The Blog-OR-sphere is abuzz with pointers to the CNN article on computer models for predicting success in the upcoming NCAA tournament featuring Joel Sokol (see the video here).  See the blog entry at Punk Rock Operations Research as well as previous entries by me and Laura on LRMC (Logistic Regression/Markov Chain) and Laura’s article on the work of Sheldon Jacobson and Doug King.  We previously saw Sheldon in articles on predicting the US Presidential election.

Getting back to the CNN article, it is a good illustration on how hard it is to write about models:

At their cores, the computer models all operate like question machines, said Jeff Sagarin, who has been doing computer ratings for USA Today since 1985.

Different people come up with different brackets because they’re asking different questions.

Sagarin’s equations ask three questions: “Who did you play, where did you play and what was the result of each specific game?” The computer keeps repeating those questions in an “infinite loop” until it comes up with a solid answer, he said.

Sagarin has arranged the formula as such partly because he thinks home-court advantage is a big deal in college basketball.

Other models ask different questions or give the questions different weights. Sokol, of Georgia Tech, for example, cares more about the win-margin than where the game was played.

Well… kinda.  It is not that Joel has a philosophical belief in win-margin versus home court.  It is simply that his models include win-margin and the resulting predictions are more accurate because they do so.  Joel didn’t go in and say “Win margin is more important than home court”:  it is the accuracy of the resulting predictions that gives that result.  Some of his models don’t include win margin at all!

I also loved the quote:

Dan Shanoff, who blogs on sports at danshanoff.com, said gut feeling is more important than statistics, but taking a look at the numbers can never hurt.

Followup question:  “So how do you know that gut feeling is more important than statistics, Dan?”.  Reponse (presumably): “Well, it is really my gut feeling, you know, since I really haven’t looked at the numbers”. [Followup added:  Dan isn’t sure he really said what he was quoted as saying.]

Be sure to check out Laura and me, and any other OR people twittering the tournament with tag #ncaa-or, starting noon Thursday.

Back at the IMA

I am at the Institute for Mathematics and its Applications at the University of Minnesota.  This brings back very fond memories.  I was a postdoc here 21 years ago at the start of my career when they had a Special Year on Applied Combinatorics.  As I recall there were 10 postdocs that year:  nine combinatorialists and me who was trained in operations research.  The combinatorialists were all scary smart and many (including Bernd Sturmfels) went on to sparkling careers.   Doing my two postdocs (in addition to the IMA, I spent a year in Bonn, Germany at Prof. Korte’s Institute) was the best thing I have done in my career.  The postdoctoral time gave me the opportunity to move past my doctoral work and to start new research directions even before I took a permanent position.  And, given I met my wife during my postdoc in Bonn, the social aspects were also wonderful.

I am speaking tonight in the IMA’s Math Matters series.  My topic is “Sports Scheduling and the Practice of Operations Research”.   The talk is open to everyone,  so if you are in the Minneapolis area, feel free to come on by!  There has already been some press on this.