Thursday, April 29, 2010

Can OR provide strategy for the World Chess Championship Players?

Among the very many great sporting events that remain hidden away from the island of the USA is the ongoing battle for the World Championship in Chess. The classy defending champion, Vishy Anand is a sentimental favorite, given that he's based in Chennai, India (Madras) where I studied. The challenger is the Bulgarian Veselin Topalov, who before the title bout started, had a slight head-head advantage over Anand. To add to this, The volcano in Iceland meant that Vishy had to endure a several-day road trip across Europe to get to the venue in time after the chess authorities only granted him an one-day extension instead of a three-day break he asked for. Vishy promptly lost the first game, but won two of the next three to open a slender one-point lead. For those who remember the Fisher-Korchnoi-Karpov-Kasparov days in the cold war era, 21st century chess still remains an incredible mental sport where supreme ego, psychological gamesmanship, and sharp analytical intellects clash to create some amazing drama.

A great blog to cover chess is maintained by Susan Polgar (one of the famous trio of Polgar sisters from Hungary) now residing in Texas. An incredible talent herself, she won an under-11 girls chess competition in her country undefeated at the age of 4, and is arguably the world's greatest female player. She asks the question - How should Topalov plan his strategy for the remaining games?

The first to reach 6.5 points in this 12-game series wins, and with Anand at 2.5 currently, a risky approach may cost Topalov many games, whereas a placid approach may enable Anand to force some quick draws (0.5 points each). I wonder what statistics, OR, and game theory has to say with regards to the optimal policy to adopt for either player?

If you are far behind in points, then it may pay to throw caution into the winds, since there is little to lose, while in the current situation, the risk and reward is still somewhat balanced.

Does a player with a lead of one point or more simply play to force quick and safe draws?

Interesting questions. Some answers would be nice.

correction (April 30) - Susan Polgar may not even be the best chess player in her family, let alone the world :-) That credit probably goes to her sister Judith Polgar.

Wednesday, April 21, 2010

The Informs Practice Conference and the OR think tank misses a trick or two

How can Informs make the Practice conference even better? An advantage of being an unofficial reporter is that I can avoid self-congratulatory blog posts and actually criticize without any sugar coating - in the hope that we get out of our comfort zone and make this an even better event next year.

Clearly some things were out of their control. All the OR folks in the world would not have been able to predict the impact of a volcano in Iceland on the travel plans of overseas visitors to the conference. Also, Dr. Micheal Trick, whose pioneering web page on O.R was the main source of information as well as inspiration for graduate students like me in the 1990s, and motivated me to join this exciting field, was missing, and one can't fault Informs for this. I was really looking forward to shaking his hands and thanking him for his service. 'Marketing in Online Social Spaces,' by Kevin Geraghty, Vice President, Research & Analytics, of 360i was a really good one (somehow I forgot to cover this in my daily conference tab). Kevin was providing an example of marketing campaigns using social networking data. He found out (using completely public domain tools!) that in the OR blog world, to the surprise of many, a certain Lieutenant in the Navy had more 'online friends' than Dr. Trick, so if one were to promote some hypothetical OR product, then he should be chosen as a first reviewer, assuming that those friends were OR types rather than 'sailors'. He also obtained other funny personal trivia from public domain, that I'll just leave out.

A second peeve I had was the highly limited lunch and dinner options for vegetarians (Two boiled asparagus roots and a turdy-looking cuboid of tofu does not an Edelman banquet make!). This should not be difficult to fix. If this doesn't change, I frankly don't see much point in shelling out two grand and semi-starve most of the conference. Thankfully, due to the purely individual initiative of the obviously superb Hilton staff, i was not totally inconvenienced. Kudos to those guys. They got their 'hospitality management OR' right.

Third, attendees should be able to obtain access to the video archive of the talks. Static slides don't cut it anymore. Unlike academic conferences, the value of practice-oriented conferences often lies in what is said in between slides.

On the positive side, the posters were a big hit. One can engage the presenters informally and in 5-10 minutes get a high-level idea of what their innovation is about. And the good thing is that you can visit them in your own time and network too. For example, I found out that the Sandia Labs in beautiful New Mexico, has this really cool Python-based modeling language (PYOMO?) that they used for stochastic programming. Can't wait to try it out. At the MPL booth, I found out that that they are making software available for free on a Windows environment. In tandem with COIN-OR (which they package MPL with, i think), you have a solid modeling and optimization package, free!

My best talks in no particular order - Sanjay Saigal (Intechne) on uncertainty , Jeffrey Cramm (Univ of Cincinnatti) on practical OR, Kevin Geraghty (360i) on social networking, John Osborne (Kroger) on OR innovation against all corporate odds, and any Edelman presentation.

overall grade: 7/10

I'll end on a warning note. The bottom line goal is that if people are thinking analytics, then O.R should not be far off from their thoughts. Well so far, O.R has been losing this battle on many fronts. Clearly, we do not want to lose our existing membership in any OR-friendly industries (most representative of the ones who showed up). However, we should be doing much more to attract members from the non-traditional, emerging industries (very few of those). At the end of the day, OR is an applied field, and while the analytics turf can be defended in journals, textbooks, and conferences, it can only be won in hard-fought battles by in-the-trenches OR foot soldiers, who need be to well-equipped and trained to build innovative, scalable, practical products and solutions for real-world problems in the 21st century - that is increasingly going to be marked by many terabytes of noisy data. When we start with "min z = c.x + y: ax <= b", O.R academic programs should first be teaching how and where to get the "a, b, c" in this and what is really means, rather than taking a short-cut straight to 'x, y, z' in the abstract world, like we have been doing the last few decades. If you have other questions, ping me and I'll tab it here ...

Tuesday, April 20, 2010

Informs Practice Conference 2010 - Day 3

The day started off with an encore presentation by the edelman winner - Indeval. Interesting talk. The theoretical stuff was not particularly interesting, but the fact that they got some OR stuff to work in real time in a mission-critical system, and involving billions of dollars is really cool. Next, i managed to attend a couple of optimization-focused talks on Approximate Dynamic Programming at Schneider Trucking, followed by 'the practice of the alternative' by Dr. Jeffrey Camm from the U of Cincinatti. He is from the Brown-Rosenthal school of practical OR, which i heartily subscribe to as well, and it was probably the most informative talk of the meet for me.

The rest of the day was devoted to the energy industry. We had another plenary by Richard O'Neill, Chief Economic Advisor to the Fed Energy Regulatory Commission. This guy went into some depth on electrical circuits and mixed integer programs. Quite unexpected, but it was great for us optimization practitioners. Then I got to listen to more presentations on energy-related topics including analytics for the smart-grid.

All in all, it was an enjoyable conference, even if one can attend only 10-12 of the 80 presentations on offer. Great location, excellent hotel service. Good job, Informs!

Monday, April 19, 2010

Informs Practice Conference 2010 - Day 2

The day started off with a plenary by a senior guy in Walt Disney. Equally interestingly, he worked at PeopleExpress decades ago, now part of Airline Revenue Management folklore. the key takeaway was that smart OR ultimately improves the odds in your favor by one or two percentage points, and that is a really big deal. Following that, there was an incredible variety of interesting topics to choose from, many of which were scheduled at the same time. So I tried to avoid MBAs, vendors, as well as academic types and listen to the in-the-trenches practice guys. The first one was the head of R&D in Kroger, a group that's 2 years old in an 126-year old company. This talk focused on how to cut thru the (126 years of ) red tape to get genuinely valuable work done. Very interesting. Quotes included "you should be willing to bet your job that your project idea works ..." and a need for passion. Every body's hand in the audience went up when he asked how many people in the audience liked their jobs. Not surprising. Practical OR is fun.

The next interesting talk was by Dr. Sanjay Saigal on probability management. He is a non-conformist and funny, and he put on a real show, and i really wished this talk had continued for another 15-20 mins. Great topic.

All in all, I missed several great talks. If anything, the practice conference has an abundance of riches in terms of the high-quality content presented. I'm distraught that I may have to skip a talk by the uber-brilliant Dr. Ellis Johnson tomorrow to catch another one at the same time that is equally exciting and pertinent to my current line of work.

One of the the 'birds of a feather' discussion in the evening focused on the role of O.R in analytics. I've already talked about the identity crisis facing OR'ers in a prior post, and INFORMS, as well as OR academic programs should act soon to fix this gap. The master of ceremonies for the Edelman awards later mentioned (or paraphrased) that OR is the most important invisible profession in the world today.

Finally, i sat in on an Edelman finalist presentation by the New Brunswick department of Transportation, Canada, since they were my sentimental pick - NB is just three hours further east of my place in Eastern Maine. In the end, the bankers won it. Interestingly, almost every single entry featured a company partnering with a university or a OR software vendor.

Today, I managed to spot two OR all-time greats, Dr. Cynthia Barnhart, and Peter Kolesar. Too bad I did not get a chance to interact with them, given that they were involved as an Edelman judge, and finalist, respectively.

Sunday, April 18, 2010

Informs Practice Conference 2010 - Day 1

Getting from North Eastern Maine to Orlando involved going thru Detriot. For some reason, this US carrier seems to 'dynamically' assign gates at DTW to arriving aircraft, so we "arrived" 30 minutes ahead of schedule, but arrived 30 minutes later. This is not the first time it's happened. Anyway, the weather is Orlando is great compared to Maine which was in the low 40s when I left ...

The workshops on Day 1 were quite useful. Forio Business solutions had some nice system dynamics tools for building snazzy looking web-simulations. I managed to get through one Markdown Optimization example, simulating different price elasticities. The next workshop was enjoyable as well as informative. Getting to to see the legendary Dr. Bixby in person was cool. Gurobi 3.0 now has a parallel barrier solver in place, and I verified that this one is deterministic. Their dev team is sure keeping a fast pace of major releases and their benchmark results continue to impress and I resolved to learn Python. Finally, the third workshop was with OPTMODEL, SAS's versatile modeling and optimization language / procedure. They displayed some nice decomposition approaches to a Kidney exchange and ATM optimization problems, all deployed within OPTMODEL. I felt that the Kidney exchange model (KEM) could have benefited from some specialized TSP subtour constraints, but then again, some nice work on display by the young OR experts from this company.

It was nice to catch up with old airline colleagues, and INFORMS had some vegetarian food, thankfully. Finally, it was nice to meet Dr. Ravi Ahuja, another O.R. giant, in person. These were the stand-out moments for day 1 - a rare chance of interacting with the stalwarts of our discipline in person.

Monday, April 12, 2010

Doogie, Darwin, Dowry, and the TSP

A couple of teenagers from the U.S. visited the beautiful IIT campus in Madras (Chennai), India in 1989-90. They were not there to attend the popular collegiate cultural festival 'Mardi Gras' as it was known back in those days, but to present a research paper on AIDS. They happened to be brothers, Balamurali Ambati, and Jayakrishna Ambati, who completed medical school at a fairly young age. Per Wikipedia, BA graduated from the Mount Sinai school of medicine at the age of 13, and become a qualified doctor at 17 in 1995.

Today, the Ambani brothers hog the media space in India as they seek to become richer, but for a brief while in the 1990s, the elder Ambati brother got entangled in a 'dowry harassment' scandal. Dowry harassment reports was big news in India, with the per-capita dowry-deaths in line with the number of 'murder for insurance' cases in the US, or the wife-beating cases in Switzerland. Anyway, reports indicate that the case fell apart after the bride's father was recorded on tape trying to extort a few hundred big ones in blackmail money. Unfortunately for the elder brother, it looks like like he had to cool his heels in India until this case was wholly resolved, losing a good two years in the "youngest achiever" race, which has since become an idiotic, even deadly craze in Southern India. This is in contrast with the more comical approach in Northern India and Pakistan, where many kids are 2-5 years older than their official age. If you were that skinny, baby-faced runt in a middle school in Bangalore, he would be that guy with the stubble in the last bench, and the captain of your school's football (soccer) and (field-) hockey teams.

Pardon the digression. Around the time the Ambati brothers visited the IITM campus (A former student reminisces here) to talk about AIDS, they were also the primary authors of this published paper on the traveling salesman problem. The title is exciting, but a tad misleading, in that it hints at a polynomial time algorithm for the NP-Hard TSP. It resembles a randomized heuristic approach based on the theory of natural selection, and appears to possess good computational properties, and has been cited more than once in followup research in this area. On the other hand, I don't think even Doogie did any OR work, real or fictional.

Sunday, April 11, 2010

All Set for the INFORMS Practice Conference

Wonders never cease. One advantage of working for a solvent company is that it provides a rare chance of attending a major conference within the U.S. The INFORMS practice conference seemed like a good choice. Besides, the annual INFORMS conference is a few months away, and one never knows how the travel budget is gonna change. A greedy approach works better here... It's been eons since the previous conference - not surprising if you spent dog-years in the mostly-bankrupt airline industry.

Given the short notice, I'm presenting absolutely nothing, get four days off from work to listen to cool OR guys talk, and the plan is just to learn as much as possible and be an on-site reporter. Please email me at shivaram (dot) subramanian (at), if you are interested in talking OR during the meet. I will be posting daily tabs of the conference here, so watch this space. If you would have liked to be at the conference but could not make it, please email me any topics you would like me to cover here, and I will do my best. As always, any tips on the optimal way to cover conferences is welcome.

For those practitioners interested in the costs involved, here's the lowdown. Airfare is about 400$. 3-4 day hotel stay is about 700-900$ (now I know how it feels to be on the receiving side of Pricing optimization). I'm staying an additional day (Sunday) to take advantage of the technology workshops and network. Registration fees for non-members is about 900$. The total cost, including daily expenses is in the ballpark of $2500. It remains to be seen if the feedback and new ideas that one can get out of this outweighs these costs. Last year's Edelman work was fantastic, and hopefully this year will be just as good.