8 March 2009 by Sanjay Saigal.

I recently mentioned LaserSearch, an engine for user-guided web search. Now comes the news that Steve Wolfram, among other things the inventor of Mathematica and author of A New Kind of Science (NKS), has also devised something new: a computation-driven semantically-aware knowledge search engine called Wolfram Alpha. (Was Alpha Wolfram taken?)

Here is Wolfram’s description of his approach:

… what about all the actual knowledge that we as humans have accumulated?

A lot of it is now on the web—in billions of pages of text. And with search engines, we can very efficiently search for specific terms and phrases in that text.

But we can’t compute from that. And in effect, we can only answer questions that have been literally asked before. We can look things up, but we can’t figure anything new out.

So how can we deal with that? Well, some people have thought the way forward must be to somehow automatically understand the natural language that exists on the web. Perhaps getting the web semantically tagged to make that easier.

But armed with Mathematica and NKS I realized there’s another way: explicitly implement methods and models, as algorithms, and explicitly curate all data so that it is immediately computable.

It’s not easy to do this. Every different kind of method and model—and data—has its own special features and character. But with a mixture of Mathematica and NKS automation, and a lot of human experts, I’m happy to say that we’ve gotten a very long way.

As with everything Wolfram touches, there is much that intrigues. Let’s suppose that Wolfram Alpha can answer a question of the following form: in which US counties did the Libertarian Party get more than 1% of the vote in the 2008 election cycle? If so, can it also compute for you the covariance of the Libertarian party’s electoral success (so to speak) with the prevalence of advanced degrees? And if it can do that, can it automatically estimate Libertarian votes in 2012 based on country demographic forecasts? Etc.

Taking the above process to its limit, can Wolfram Alpha – say, sometime in the distant future – become an all-purpose web-based Analytics engine?

Posted in Business Intelligence | 1 Comment »

6 March 2009 by Sanjay Saigal.

The primary professional society for advanced analytics – INFORMS – has a distinguished history and an impressive membership. But like most volunteer-driven groups, INFORMS operates on the basis of consensus and professional fellowship. It is emphatically not an opportunity-driven enterprise akin to a private company or even a lobbying-savvy professional group such as the American Medical Association.

This sort of self-branding – as an agency for the advancement of a specialized kind of knowledge rather than as a guild devoted to nurturing and expanding professional hegemony – affects both the operation of INFORMS and the development of the profession. An interesting manifestation of this phenomenon is the slow adoption of information technology by INFORMS. Things are, however, improving: As of today, INFORMS boasts an official blog!

This official blog doesn’t quite get us to INFORMS 2.0; it’s still one-way communication. The society has supported blogging at previous national-level meetings through the efforts of individual INFORMS Computing Society (ICS) members (see here). And the very nifty eNews Daily, which debuted at last year’s Washington, DC meeting, looks to me like a keeper.

I anticipate that these efforts will take a more definite form over time, to the point that non-attendee members (as well as the interested public) can feel connected to events as they occur. The nominal goal, of course, is to increase the dispersion and penetration of the profession’s message. But more interestingly, proliferating Web 2.0 technologies should increase the engagement of INFORMS members in the society’s affairs and the attractiveness of its scheduled events.

A milestone of the development of Web 2.0 ideas within INFORMS should appear in late April, from the 2009 Practice Meeting in Phoenix, AZ. The Marketing folks at the society are mulling over what should and could be done. Let them know! Are you planning to attend? If so, does the prospect of (you) blogging from the meeting grab you? Does it seem like unnecessary work when you’d rather be schmoozing with grad school friends? Does it raise the question, “would anyone want to read my impressions?”

And if you are not planning to attend, what might most make you keenly regret your decision not to? Would blogposts help you better stay in touch with goings-on at the meeting? Or is something like the aforementioned eNews Daily already too much information? Or perhaps, going for a diametrically opposed extreme point, do you wish someone would set up an INFORMS Twitter feed?

Posted in INFORMS, Operations Research | 5 Comments »

27 February 2009 by Sanjay Saigal.

While upgrading a portfolio planning model implemented in Microsoft Excel, the need arose to validate a complex simulation involving log-normal distributions. The log-normal probability distribution is obtained by taking the logarithm of exponentiating (UPDATED: 3/1/09) the ubiquitous normal distribution. Its applications are common enough for some researchers to propose that the log-normal deserves at least equal billing, if not center stage.

The need was to back-calculate the mean and variance of the log-normal distribution using certain other known measures. This required non-trivial nonlinear manipulation, an activity that reminded me of the time lapsed since I last engaged in open-ended mathematical discovery. Which brought me to the question: mathematical sophistication is clearly necessary for Analytics, but is it significant? And if not, what skills are required in an Analytics practitioner?

The business pundit Peter Drucker wrote (h/t to J. D. Meier):

When “operations research” first came in, several of the brilliant young practitioners published their prescription for the operations researcher of tomorrow.  They always came out asking for a polymath knowing everything and capable of doing superior and original work in every area of human knowledge.  According to one of these studies, operations researchers need to have advanced knowledge in sixty-two or so major scientific and humanistic disciplines.  If such a person could be found, he would, I am afraid, be totally wasted on studies of inventory levels or on the programming of production schedules.

Though exaggerating for effect, Drucker is asking a good question about feasibility. Few of us can be Feynman! As Analytics moves from being a “nice to have” to a “must have”, the appropriateness of the training of its frontline soldiers becomes increasingly critical. As described elsewhere here, and elsewhere (the issue is elegantly covered at a high level here by Jim Orlin), the INFORMS professional society is stepping to the challenge.

Like many, perhaps most, Analytics professionals I add value through the modeling and implementation of decision-support techniques, not by creating new mathematics. However, my training was almost entirely mathematical. Even now, graduate training tends to over-focus on mathematical technologies. But for professional success, the Analytics practitioner requires a broad set of divergent skills beyond math.

Some skills – facility with optimization and simulation techniques, statistics, certain aspects of software engineering – can be effectively channeled through higher education’s delivery model. But other, equally important, skills cannot. For instance, project management cannot be taught, only learned through the process of doing. (It especially cannot be taught by academics with zero IT project experience.) Critical skills such as business communication, spreadsheet-based analysis and team effectiveness are best left to the in-service setting. (See this online version of the 2007 Interfaces article by Sodhi et al for a list of commonly expected OR skills.)

The academic part of the profession has focused on core technical skills. Is it the role of Analytics professionals to fill in the picture?

Posted in Education, Operations Research, Intechné | 6 Comments »

18 February 2009 by Sanjay Saigal.

Researchers at the Arizona State University have prototyped an interactive linear programming-based meta-search tool called LaserSearch. The online documentation does not explain how the underlying search is implemented. (Basic search results are similar to, but don’t map exactly to Google or Yahoo output.) LaserSearch implements user-driven iterative refinement: on the basic results page you indicate relevance by clicking green (highly relevant), yellow (somewhat relevant) and red (not relevant) buttons next to each URL. Clicking Improve refines the results. According to one of the authors, Asim Roy, each click on Improve triggers the solution of a small linear programming problems that sifts through the flood of results for high-value URLs.

I have tried out the prototype, but despite the “OR Inside”, I have yet to understand its filtering logic. For instance, here are the top three results of a search for “norwegian wood”.

The first URL points to Murakami’s novel with that title, the second to the Wikipedia entry for the Beatles song, and the third to a video on Youtube. So far so good. Since I was interested in the Beatles song, I clicked the red button (i.e., irrelevant) next to the first entry, the star (indicating “more relevant”, which also activates the green button) for the second, and the green button for the third. Then I clicked on Improve, which brought up the following screen. The top seven results do, in fact, concern the Beatles song. So LaserSearch clearly promoted results related to the Beatles song. However, Murakami’s novel reappears in slot 8, as do two other non-Beatles references in slots 9 and 11.

Shouldn’t the lowest-possible ranking of the novel on the first results screen essentially remove it from succeeding searches? I don’t know. Perhaps further experimentation will yield more comprehensible results.

If you choose to try out LaserSearch – and I encourage you to do so – be warned, the prototype is somewhat fragile. As I was testing it over a period of 30 minutes, it crashed once and generated empty results screens a couple of times. But for an alpha version, it works well enough.

As for understanding its logic, perhaps it is necessary to read the associated paper. Titled An Interactive Search Method Based on User Preferences, it was published in the December 2008 issue of the journal Decision Analysis.

Posted in Operations Research | 2 Comments »

13 February 2009 by Sanjay Saigal.

“It was a glittering time. They confidently swept into office, ready, moving, generating their style, their confidence – they were going to get America moving again. There was a sense that these were brilliant men, men of force, not cruel, not harsh, but men who acted rather than waited. There was no time to wait, history did not permit that luxury; if we waited that would all be past us… Things were going to get be done and it was going to be great fun; challenges awaited and these men did not doubt their capacity to answer these challenges… History summoned them, it summoned us: there was little time to lose.”

Halberstam’s breathy description of the DC gestalt ca. JFK’s inauguration is curiously (and scarily) applicable to today’s America. Ascribing the opposition’s intransigence to mere habit, the Administration is charging ahead to evaluate, diagnose and fix the problems bedeviling our world. This attitude bodes well for researchers of all stripes. A recent email from a major university administrator contained the following phrase - “the campus expects a brief open window of riches”. Things are going to be done and it is going to be great fun!

In this climate of transparent, analytically-driven, decision-making from top to bottom, how does the profession measure up? On the one hand, Operations Research academics are doing what they can to capture the riches soon to rain down from Mt. Washington. However, it’s really interesting on the commercial side of the fence. Especially among vendors, much activity is afoot:

• I mentioned Gurobi’s surprisingly mature LP/MIP solver here. The start-up has taken a tack of ubiquity – making the product available in as many optimization environments as possible. In addition to Excel-compatibility through Frontline’s Solver framework (see Frontline CEO Dan Fylstra’s comment), the optimizer is available in conjunction with three leading algebraic modeling languages, AIMMS, GAMS and MPL. I understand that a wrapper for AMPL is also in process.
• Interestingly, Gurobi is undercutting the price floor maintained by the previously comfortable duopoly of the two benchmark solvers: CPLEX and XPRESS. Instead of $15,000 or more per seat, Gurobi is asking approximately half the amount. While the impact of per-seat license fees in the adoption of optimization technologies is routinely exaggerated, cutting the price in half will definitely perturb the status quo. (And cause not a little consternation in Ilog’s – IBM’s, if you will - executive suite, which has come to depend on CPLEX’s profitability. I suspect that Fair Isaac will be less impacted, since its optimization-based direct revenues represent a much smaller part of its profitability.) Gurobi has not yet shared its deployment pricing model. That will determine its uptake in the significant optimization ISV market.
• In August 2008, Microsoft soft-launched a .NET-oriented optimization framework called Microsoft Solver Foundation (MSF). In addition to a rich .NET API, MSF can also be used as an Excel add-in. (Surprisingly, it does not particularly share the elegance of integration with Excel evident in Frontline’s products.) MSF 1.1, introduced today, even includes Gurobi’s MIP solver (was it code-named Zelig?!) as the default. This very smart choice should make it a powerful solver alternative, especially in small shops, which should be able to use it free for internal use. Longer-term, MSF’s integrative framework designed to incorporate third-party optimizers, backed by the sales heft of Microsoft, could make it a product to be reckoned with.
• SAS Institute, a major player in the Analytics space, has sharpened its focus in the optimization space in recent years. As a privately-held company, its actions are often opaque. SAS’ OR group has recently been in an aggressive hiring mode, though I remain more impressed by the effort than any (known) star hires. Further, its marketing seems to be targeted at its existing customer base. Admittedly, the base is large and lucrative. But it’s difficult to visualize such a narrowly-focused effort expanding its mindshare in the broader market.
• IBM’s acquisition of Ilog and Fair Isaac’s acquisition of Dash Optimization have been written about here and elsewhere. FI is using Dash’s XPRESS engine to extend its largely financial services-based business. Unless the company has a more expansive strategy up its sleeve, that seems like fairly limited leverage. IBM, on the other hand, is selling a fairly pervasive strategy for Ilog’s Optimization and Rules products. Even after filtering out the more egregious spin, the combination of IBM’s consulting reach and its sales prowess cannot but have a multiplicative impact on Ilog’s core strength: technology.

All in all, 2009-2010 promises to be the mother of all “interesting times” for Analytics.

Posted in Operations Research, Vision | 3 Comments »

4 February 2009 by Sanjay Saigal.

Exiting graduate school in ‘91, I interviewed with the Thinking Machines Corporation (TMC). It was a job for which I was woefully unqualified. No surprise, I didn’t get the chance to find out. And anyway, in two years, the company had gone under, victimized by being ahead of its time. But for the ten years it was in existence, TMC burned a spectacular trail through applied computation science. Inarguably its brightest light was the physicist Richard Feynman. (TMC founder Daniel Hillis affectionately recounted their collaboration in Physics Today, and you can read it here.)

Feynman’s legend as a Javert-like pursuer of enlightenment is well-established. (See, for instance, the Feynman tribute site.) Sadly, set next to his spectacular Physics work, Feynman’s contributions to analytic decision-making are less well-known. Hillis’ article described some of Feynman’s pioneering work on the numerics of the Connection Machine. But more interesting to me is Feynman’s work on the Challenger disaster commission.
Alone among the “wise men” on the commission, Feynman went to the source – interviewing the shuttle engineers whose 1 in 100 failure estimate magically inflated to 1 in 100,000 in the hands of NASA management! His appendix to the final report is worth reading as a primer on (desirable) structured design and (self-deluding) risk management. For instance, here is Feynman talking about how shuttle uniquely engines were built:

The usual way that such engines are designed (for military or civilian aircraft) may be called the component system, or bottom-up design. First it is necessary to thoroughly understand the properties and limitations of the materials to be used (for turbine blades, for example), and tests are begun in experimental rigs to determine those. With this knowledge larger component parts (such as bearings) are designed and tested individually. As deficiencies and design errors are noted they are corrected and verified with further testing. Since one tests only parts at a time these tests and modifications are not overly expensive. Finally one works up to the final design of the entire engine, to the necessary specifications. There is a good chance, by this time that the engine will generally succeed, or that any failures are easily isolated and analyzed because the failure modes, limitations of materials, etc., are so well understood. There is a very good chance that the modifications to the engine to get around the final difficulties are not very hard to make, for most of the serious problems have already been discovered and dealt with in the earlier, less expensive, stages of the process.

The Space Shuttle Main Engine was handled in a different manner, top down, we might say. The engine was designed and put together all at once with relatively little detailed preliminary study of the material and components. Then when troubles are found in the bearings, turbine blades, coolant pipes, etc., it is more expensive and difficult to discover the causes and make changes. For example, cracks have been found in the turbine blades of the high pressure oxygen turbopump. Are they caused by flaws in the material, the effect of the oxygen atmosphere on the properties of the material, the thermal stresses of startup or shutdown, the vibration and stresses of steady running, or mainly at some resonance at certain speeds, etc.? How long can we run from crack initiation to crack failure, and how does this depend on power level? Using the completed engine as a test bed to resolve such questions is extremely expensive. One does not wish to lose an entire engine in order to find out where and how failure occurs. Yet, an accurate knowledge of this information is essential to acquire a confidence in the engine reliability in use. Without detailed understanding, confidence can not be attained.

A bottom-up approach is equally essential for building robust and sustainable Analytics-driven decision-support systems. Without the benefit of well-tested atomic models (e.g., the peculiar demand for fundamentally different types of products), building a large-scale model ab initio (in this instance, a manufacturing company’s demand forecast) invites shelfware-hood. I have seen exactly this sort of failure occur at a multi-billion dollar world-wide ERP roll-out, where the demand planning model template built by HQ analysts was so inapplicable to specific business units that local planners took to over-writing official forecasts produced by the ERP with their own hand-computed numbers!

As I’ve previously described (e.g., here), the practice of Analytics inevitably occurs in the shadow of business imperatives. Business goals give shape to the analysis. But they also have the power to corrupt the process. Feynman pungently captures that corruption at NASA, and its consequences in his final words:

For a successful technology, reality must take precedence over public relations, for nature cannot be fooled.

One wonders about Feynman’s analysis of the current financial crises, which appears at least as much a product of self-delusion on high as the Challenger disaster!

Posted in Methodology, Operations Research, Risk | 3 Comments »

30 January 2009 by Sanjay Saigal.

The market in optimization software is experiencing a state of turbulence last seen in the mid-eighties, when OSL and CPLEX were fighting for dominance. CPLEX won that war, not simply because it was competitive on benchmark models, but by being better engineered, and later, better marketed. With the perspective of 20+ years, Bob Bixby’s decisions – writing in C rather than FORTRAN, centralizing optimizer usage on an API/library rather than an interactive system, focusing on building a market by targeting value-added software vendors rather than just OR professionals – seem obvious. But at the time, they were quite unorthodox.

From the viewpoint of one privileged to witness the development of CPLEX at close range (Bob directed my thesis), the second major factor accounting for CPLEX’s success was its exceptional product R&D team that came together in the mid-late nineties. Its two generals were Ed Rothberg, who came over from the legendary parallel numerical computation group at Silicon Graphics, and, later, Zonghao Gu, a Lindo escapee.

Ed went on to lead CPLEX into the realm of reliably solving mixed-integer programs (MIPs) by smartly adapting academic research on cutting plane methods. To be fair, in the process, Ed, Gu, and the rest of the team created a fair bit of (largely unpublished, for competitivee reasons) new computational science. By the time Ed moved on to real-time semiconductor scheduling, Gu was ready to captain what had become the 800 pound gorilla of the optimization space. For a variety of reasons, in 2008 Bixby, Gu, and Rothberg left Ilog (CPLEX’s home since 1997) and started their own venture, rather unimaginatively called Gurobi Optimization. (Who is who in the picture is left as an exercise to the reader!)

I learned to my surprise that Gurobi planned to build a linear and mixed-integer code from the ground up. First, there was the obvious competitive angle vis-a-vis Ilog – they would have to start from absolute ground zero. Not even a line of CPLEX code could make it into their solver. Secondly, there was the question “why?” Having already built CPLEX into a lasting success, why would they wish to go over the same ground again? I confess that the question is still open. Nevertheless, more power to them, because it is becoming clear, that we may have a new contender on our hands. Via Mike Trick, I learn this morning of recently released third-party benchmarks comparing the performance of Gurobi’s as-yet-unreleased optimizer and CPLEX’s latest release.

Optimizer benchmarks are best taken with a great deal of caution. However, what these results suggest is nothing short of stunning: Less than a year in development, Gurobi is essentially competitive with CPLEX. On a 74-problem MIP test-set:

• Gurobi solves MIPs faster on single-processor machines: It beats or equals CPLEX’s performance 55% of the time. (A third solver – MOSEK – is also compared. It wins or ties for first 5% of the time.)
• Gurobi parallelizes robustly: Having used it in a number of projects over the years, I can attest that CPLEX’s parallel branch and bound is a very solid piece of code. In this one-on-one comparison on a 4-processor machine, Gurobi wins or ties CPLEX 58% of the time.
• Aggregate solution times are less on Gurobi: Considering only problems on which at least one integer solution was found, on a single-CPU system Gurobi runs through the test-set in 25% less time than CPLEX, as measured using the geometric mean of times. On 4-CPU systems, the improvement is still considerable – 15%.
• Gurobi is good at finding integer feasible solutions: CPLEX fails to identify a single integer feasible solution on 2 instances in either mode. Gurobi fails on one instance in single-threaded mode. It finds at least one integer solution on all test-set problems when using four processors.
• CPLEX takes better advantage of parallelization: CPLEX’s speed-up in going from one to four processors is 40%, whereas Gurobi only manages 30%.