Tuesday, November 9, 2010

MIP feasible completions and the wheel of fortune

First the 'talk of the town'. The miraculous wheel of fortune solution using a single letter.



Initial feedback suggests rigging etc, but to OR'ers this 'hole in one' should not come as a drastic surprise. After all, this occurrence is infrequent but not impossible. One can pose this puzzle as an MIP (or solve using constraint programming), using binary variables to represent letter-choices for every blank, along with additional constraints that ensure that words are selected from a dictionary, while also ensuring that the sentence is grammatically correct, and so on. Of course, it would be a rather unwieldy MIP and a pure generic-solver approach may take forever. However, by exploiting the language structure and leveraging our learning from prior experience with the kinds of phrases that typically show up in WOF, it should be possible to significantly reduce the number of combinations to be explicitly explored. Note that only one such feasible solution is the right answer to the original WOF puzzle and to guarantee this, one usually needs more letters to be exposed to break ties. Isn't that how the miracle workers at Bletchley park cracked the Enigma codes in WW2 and began solving 'puzzles' fast enough to make that information usable?

Real-world MIPs often have such hidden structures that our customers understand far better than pure OR types. I was constantly impressed that the resident real-time crew schedulers at United Airlines would routinely come up with remarkably good quality feasible crew pairings (partial schedules) at the drop of a hat that would make us OR PhDs look so stuffy! Such crew pairings have to satisfy a myriad of FAA and company-negotiated "nonlinear and non-convex" work rules to confirm feasibility.

Another important aspect of real world decision problems is that the line between feasibility and infeasibility is often blurred. For example, look at the snippet from this email i received recently. It's one of those that get forwarded around and comes back to haunt your inbox once every two years.

"
I cdnuolt blveiee that I cluod aulaclty uesdnatnrd what I was rdanieg. The phaonmneal pweor of the hmuan mnid, aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it dseno't mtaetr in what oerdr the ltteres in a word are, the olny iproamtnt tihng is that the frsit and last ltteer be in the rghit pclae. The rset can be a taotl mses and you can still raed it whotuit a pboerlm. This is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the word as a wlohe. Azanmig huh? Yaeh and I awlyas tghuhot slpeling was ipmorantt! If you can raed this forwrad it "

Posed as an MIP, almost every one these partial solutions (words) is tragically infeasible, and yet, can be perfectly interpreted by the end user in real-time and combined into a wholly understandable paragraph.

The point is that many abstract MIPs may be hard to solve, but in almost all real life instances, there is plenty of additional information from the real world that typically helps us generate meaningful business answers via such math models. If we do it the right way, NP-Hardness rarely leads to a business issue. The combination of good OR skills, MIP solvers, and domain expertise can solve complex business decision problems in real-life quickly enough to let customers gain a tangible competitive advantage.

No comments:

Post a Comment