January 2008 – Mike Trick's Operations Research Blog

Dice, Games, and ORStat

Last year, I received a paper from Prof. Henk Tijms of the Vrije University Amsterdam on using stochastic dynamic programming to analyze some simple dice games (pdf version available). A few years ago, I tried to do something similar with an analysis of a game I called Flip, but which is more commonly known as “Close the Box” (the paper appeared in INFORMS Transactions on Education). Both Tijms’ work and mine spend a fair amount of time discussing how well certain easy heuristics do relative to optimal decision making in simple games. Ideally, heuristics would get good, but not optimal solutions: that would make the game challenging as players tried to come up with better and better heuristics. For “Close the Box”, while the optimal decision was quite subtle, some simple heuristics got pretty close (perhaps too close to discern the difference). These games make good classroom demonstrations and even better mini-projects for summer schools and the like. Tijms’ paper was written for a journal aimed at students.

Tijms has also done the field a great service by making his software for applied probability available, which are good tools for education. Check it out at his web page.

Operations Research to Decide the Election?

Brian Borchers wrote me to comment on an article in the New York Times on how the US primaries are moving into a phase characterized by complicated resource allocation problems. Up until now, it was easy: candidates could spend their time in Iowa and New Hampshire (then Nevada and South Carolina) and not feel overstretched. But with those primaries and caucuses now past, it gets more complicated. Tuesday February 5 is “Super Tuesday” when 24 states are to choose their delegates to the national convention. No candidate can reasonably campaign in all parts in all of these states. But the rules on how delegates are chose make it necessary:

…the delegate rules for Democrats and for Republicans are different and, within each party, often vary from state to state. For example, the Republicans have some states where the statewide winner gets all the delegates, providing an obvious target for a candidate who might seem strong there. Among them are Missouri, New Jersey, New York and Utah.

But there are other states where the delegates are allocated by Congressional district, sometimes winner-take-all, and sometimes proportionally.

By contrast, Democrats eliminated the so-called winner-take-all rules. Instead, delegates are allocated depending on the percentage of vote each candidate gets in a Congressional district, under very expansive rules that, generally speaking, mean the candidates divide the trove evenly assuming they get more than 30 percent of the vote. There are also some delegates allocated statewide, again proportionately.

As Brian summarizes:

The various political campaigns have been building statistical models to predict voting outcomes in different congressional districts and using these as the basis for game theoretic decisions about how best to spend their limited funds and limited candidate time. The more traditional polling approach isn’t adequate, because it would be too expensive to do separate polls for every congressional district…

This is an interesting game involving things like parity (if there are 2 delegates for a district, then it is enough to get 34% of the vote to get 1; with 3 candidates, 51% can earn you 2 delegates), resource allocation, timing (Rudy Giuliani chose to skip the initial rounds to concentrate on Florida and the Super Tuesday states, perhaps losing too much “momentum” in the process) and so on. Since it has been a while since both the Democratic and Republican races have been this open, this should spur interest in this sort of modeling. Punk Rock Operations Research has a posting on forecasting and polling, but that should only be the data for making better decisions. I would love to hear of any real operations research being used by the campaigns.

Simulation and the NHL playoffs

Growing up in Winnipeg, Canada (city motto: “At least it is a dry cold”), I had a short and rather forgettable hockey career (though getting a shutout as a goalie at 12 years old remains one of my favorite memories). I have been greatly outdone by my nephew Mathieu, who actually looks like he knows what he is doing when facing a shot. Since then, I follow hockey mainly through my local team, the Pittsburgh Penguins. I have been lucky to see a number of amazing players on the Penguins: Lemieux, Jagr, and “Sid the Kid” Crosby perhaps best of all. I keep hoping to provide the schedule for the NHL, which I think is the only thing that would impress my buddies back in Winnipeg.

Armann Ingolfsson of the University of Alberta has appeared in an article in the Toronto Sun on using simulation to predict who will make the playoffs this year. You can read a more detailed description of what he does in an article published in the INFORMS Transactions on Education in 2004. The main idea is to use simulation to generate 500 possible continuations of the regular season and to determine how often every team makes the playoffs. A critical feature of this is the ability to assign probabilities of wins for every game.

I am very happy to see that the Penguins currently have a 92% chance of making the playoffs. But the system doesn’t take into account that Crosby has a “high ankle sprain” keeping him out for two months. That might knock off a percentage point or two.

Dash Optimization is acquired by Fair Isaac

Dash Optimization, makers of Xpress-MP (one of the two leading linear and integer programming solvers, along with ILOG’s CPLEX), has been acquired by Fair Isaac. Fair Isaac is an anaytical application company, known best for their credit rating systems (they do the FICO scores that companies use to determine whether to extend credit). This is an interesting move. On one hand, we have a premier OR company being acquired by a company that is not particularly known in the OR world (despite their analytical focus). Will Xpress-MP be forgotten, particularly as the credit market is troubled? Will Xpress-MP continue to be a available and supported for the broader world?

On the other hand, a very well-known company now has operations research software as a key aspect of their offerings. Will they be able to leverage this to extend the reach of OR to more firms? One nice line of their press release:

We will showcase the Dash products and introduce our clients to these capabilities at the forthcoming InterACT conferences in Vienna and San Francisco.

Having OR methods showcased by Fair Isaac could be a huge boon to the field. If companies think “Fair Isaac is investing in OR, maybe we should find out more about the field”, that would be great! But one potentially worrisome aspect of the press release:

With Dash part of Fair Isaac, we can do more to:

Incorporate an additional layer of analytic power into our industry-standard solutions

Create advanced custom solutions based on specific client needs

Develop innovative new solutions for large and complex business problems

How much will Fair Isaac keep within itself rather than provide core optimization products to the wider world? The longer press release calms fears about the role Dash software will play:

Fair Isaac’s acquisition of Dash builds upon a longstanding partnership between the two firms. Dash optimization technology is currently embedded in Fair Isaac’s Decision Optimizer, a software tool for achieving the smartest decision strategies given operational complexities, resource constraints and market uncertainties.

“Demand for sophisticated decision management tools is growing rapidly, and the addition of Dash optimization technology to our portfolio helps us to remain the market leader,” said Mark Greene, CEO of Fair Isaac. “With their optimization capabilities and our own business rules management and predictive analytic solutions, Fair Isaac now has the industry’s most comprehensive decision management suite.”

Being part of a “decision management suite” seems good!

There is a discussion of this on the USENET group sci.opresearch. In the discussion, Bob Daniels, one of the founders of Dash Optimization, talks about the change:

The good news for Xpress-MP and its users is that ALL the Dash employees are
moving enthusiastically to Fair Isaac and the development budget is
considerably enhanced.

For those of you who don’t know, the name “Dash” comes from (Bob) Daniel and
(Robert) ASHford. Robert and I, and the team we have recruited, have been
developing Xpress-MP for over two decades and we weren’t about to sell our
“baby” to people who weren’t dedicated to Math Programming and Xpress-MP. Of
course, we the founders have moved to Fair Isaac too.

Best wishes to Bob Daniels and the rest of the Dash Optimization team in making this transition from a stand-alone company to part of a much bigger operation. And let’s hope that Xpress-MP continues to get better and better (and not just for the use of Fair Isaac!).

IFORS 2008: Time to get your abstracts in!

I just posted this in sci.op-research and comp.constraints

There is still time to get your abstracts in for IFORS 2008. IFORS
(International Federation of Operational Research Societies) is an
umbrella organization for national OR societies. Every three years,
IFORS holds a conference. Recent past conferences have been in
Edinburgh and Hawaii. In 2008, the conference will be held in
Sandton, South Africa. Sandton is a suburb of Johannesburg, and has
outstanding conference facilities (I am a VP of IFORS, so I visited
the site two years ago). The conference is shaping up to be a very
interesting one, with an emphasis on how OR enhances and links
communities. The dates of the conference are July 13-18 and all the
info you need is at http://www.ifors2008.org

In addition to a top-notch scientific program, Sandton offers some
great outings, before, after, or during (IFORS conferences have a
traditional Wednesday outing) the conference. I particularly enjoyed
visiting Soweto as well as the “Cradle of Humankind”. I also highly
recommend visiting Cape Town (though winter weather there can be a
little dicey: there is a reason all those ships are sunk at the
Cape!). Right now, I am checking out safaris (winter is a great
time, since the animals are easier both to find and to see).

Due to restrictions at the convention center in Sandton, we won’t be
able to keep accepting abstracts after January 31, so get your
abstracts in!

If you have any questions or concerns, please don’t hesitate to write
me.

I really did enjoy the trip two years ago and am very much looking forward to this year’s conference.

Passing of Rick Rosenthal

Update Jan 10. A webcast celebrating Rick’s life will be available live starting at 1:30PM PT on January 10.

This is a post I had hoped to not make. Rick Rosenthal of the Naval Postgraduate School has passed away following a long, courageous, and inspiring fight with cancer. In my list of those I admire and hope to emulate in this field, Rick was right at the top. As a researcher, he represented everything I admire: insight, brilliance, and real wish to affect practice. As a person, he was honorable, thoughtful, funny, and inspiring. The field of OR is lessened by his passing. I consider my life to have been greatly enrichened by knowing him and I am thankful I knew him well enough to consider him a friend. My thoughts are with Pascale and the rest of Rick’s family.

Here is the message from the head of OR, James Eagle, at the Naval Postgraduate School (thanks to Jerry Brown for sending it on to me):

Distinguished Professor Richard E. Rosenthal died at approximately 1 pm, Thursday, 3 January 2008 at the Hospice of the Central Coast, Monterey, CA, after a courageous bout with cancer. He was with family and friends at the end. A private memorial service is planned for Sunday, 6 January. Prof. Rosenthal was born in 1950 in Nassau County, NY. He graduated from John Hopkins University in Mathematics in 1972 and from Georgia Institute of Technology in Operations Research (OR) in 1975. From 1975 to 1983 he was an assistant and associate professor of Management Science at the University of Tennessee. In 1984 he came the OR Department at NPS as a National Academy of Sciences Senior Research Fellow. He stayed at NPS as an associate, full, and distinguished professor. He was Operations Research department chairman during 1997-2000. He has authored or co-authored over 20 professional papers in the OR literature. His numerous awards include the International Federation of Operations Research Societies Distinguished Lectureship, the Department of the Navy Meritorious Civilian Service Award, and the Institute for Operations Research and the Management Sciences Prize for Teaching OR/MS Practice. The Military Operations Research Society has recently established the Rosenthal Student Military Modeling Award to recognize outstanding student military operations research. A public memorial service will be scheduled at the Naval Postgraduate School.

Rick has requested the following:

“In lieu of flowers, please:

1- Take time off from your responsibilities to enjoy a great meal with good friends and family who you do not see often enough,

2- Give some time or money to a charity that brings some joy to those who need it or contributes to advances in education, science, the arts or the environment.”

The Rosenthal mailing address is 11 Encina Avenue, Monterey, CA 93940.

January 5 update. As news of Rick’s passing spreads, there will be more posts from all those he touched. A Naval officer and student of Rick’s has posted here. He points to Rick’s blog on his fight, a blog I followed but am now finding too hard to read.

End of INFORMS Resources Page?

In 1994 I began collecting links about operations research on the internet. Of course, it was pretty easy at the time. There were only about 1000 web servers at all, so there were just a handful of OR links. But there was also gopher and ftp, so I could put together a pretty good page with 30 or so entries. Over time, “Michael Trick’s Operations Research Page” grew and grew, encompassing a couple thousand pointers. It is through that page that I became involved in INFORMS, by becoming the founding editor of INFORMS Online.

In late 2000, I finished my terms as editor, but was then elected President of INFORMS (I suspect MTORP had something to do with that). At that time, I donated MTORP to INFORMS, where it became the INFORMS OR Resource page. At the time, it was the second most accessed page at INFORMS (next to the conference page). I continued to edit the page, primarily because the software made it pretty easy to do.

Over the past few years, I have been thinking that the time for the resource collection is pretty well over. The page was started long before google, and played an important role when finding information on the web was hard. With google and its competitors, that is no longer the case. A quick search can find any page on the web in an instant. If I want to find something about OR, I go to google, not the OR Resources page.

The page is actually taking more time these days. Spammers attack the page, and integrating the system in the overall INFORMS Online system is a hassle. The worst aspect is updating the page. About 1/3 of the links are no longer valid, but correcting everything needs to be done by hand. So I am thinking perhaps the time for the system is over. What do you think? I see three choices, though I am sure there are more. I (we) could:

Shut down the page, perhaps replacing it by an edited blog on what’s new on the web in OR (similar to this blog, perhaps).
Continue to limp along about the way we are doing things.
Find someone else to come in, provide direction and excitement and show what a resource pointer collection can really be!

So, I’m interested: what do you think we should do?