Saturday, June 30, 2012

Alternative Optimal Solutions and Combinatorial Risk

Optimization in practice is usually not just about setting up a well-behaved model with an objective function and finding 'the optimal answer'. While that is an interesting exercise, the real 'value add' comes from the subsequent process of recognizing the business reality that a practical decision problem typically has many answers. Consequently, analyzing alternative optimal solutions in a way that is useful to the client is quite important. In other words, practical optimization is more often about analyzing feasible alternatives that initially appear to be equal to us, but in reality have vastly different qualities from our client's point of view (note: returning 'infeasible' is not really an option, and showing why our model returned 'infeasible' is only slightly more useful).  As we initiate a dialogue with our client to understand these differences and the context in which some alternatives are better than the others, we can see our lab model gradually transform into a useful business analytics tool.

Cutting across industries, I have not yet come across a single optimization problem deployed in production that does not have multiple objectives. Every seller loves to maximize profit, but not at the cost of losing out on volume or sales dollars in the process. Over time, the number and priority of such considerations change. For example, in the airline industry,  it is not uncommon for large-scale crew schedule planning problems to have hundreds of different goals and priorities. The richer the solution space, the more the number of goals it seems. In fact, optimizing just a single measure is risky because such a gain ("extreme point") almost always comes at the expense of other metrics that haven't been included within the analysis yet. Which leads us to:

Combinatorial Risk
This hidden problem of 'risk', even within a deterministic modeling context, is exacerbated in combinatorial (or global) optimization situations. Here, our model analyzes multiple inter-linked decisions that can produce solutions that radical differ from current practice and looks great numerically, but in reality, can potentially hurt our client's business if actually used. 'Locally optimal' does not always and automatically mean 'inefficient'. Like globalization, combinatorial or global optimization based holistic decision making can and does bring in more efficiency and profitability compared to that obtained by combining multiple locally optimal decisions when things go as per forecast. On the other hand, if the alternative (near-) optimal scenarios along with their corresponding risk of failure are not well mapped out and thought through, the resultant machine-generated combinatorial solution can cascade the risk of a bad decision through the system.

Part-3 here.

Thursday, June 28, 2012

Time-lapse view of a Soap Opera

One can speed-watch a bad 3-hour Shah Rukh Khan Hindi movie, set in some implausible post-modern world, in 15 minutes or less, and yet fully grasp the plot and story. Somewhere down the line, those wonderfully poetic song-and-artistic-dance filled world of authentically Indian movies and television programming disappeared, and along with it, my patience, leading to this compressed viewing method. On the other hand, it turned out to be quite interesting watching Jack Bauer save the U.S from annihilation in a '24' hour day, over a contiguous 24 hour period (on DVD) without any cuts. This provided a completely different experience and understanding compared to watching '24' live one-hour capsules across 24 weeks.

To experiment with a larger data set, I decided to watch a popular (5 days a week) Hindi TV serial that achieved high viewership ratings over its two-year lifetime (2008-10), and whose episodes were meticulously labeled and archived on the net by some fans. That data set had about 520 observations (episodes), which I speed-parsed over an exhausting six week period.

A TV Serial Storyline is a Random Process
Time-lapse viewing allows one to recall past events and key plot twists relatively more clearly, thus making it a little easier to figure out the 'rate' at which the storyline converges. If you think of a TV serial storyline as an origin-destination path that passes through a number of intermediate and interlinked stages (or states), you can identify the type of state transitions, including the many instances of 'back to square one' in a time-lapse mode. The soap storyline returns to a previously visited state (i.e. cycles or sub-tours) with a significant nonzero probability, much to the viewer's chagrin. You can also spot the random walks where the storyline drifts away from the original theme. When these events happen too often in soaps, it is a dead-giveaway that the plot is on life-support and the plug will be pulled shortly.

The story line of most TV serials appear to be remarkably Markovian in design. If you were to watch the series in real time (i.e. slowly), you would be able to skip many episodes and yet rejoin in a few weeks without really missing anything. In a soap opera, the future is indeed independent of the past, given the present.

Another O.R analogy
There are some intermediate episodes that generate peak ratings and a spike in viewer comments in the online archive. These often turn out to be events that appear to be 'pivotal' in the sense that they promise a lot of exciting ripple effects down the road. There is just the right amount of uncertainty in the future trajectory of the storyline but with some enticing structure around it. For example, if you were to look back at the Harry Potter book series, this would be around year 4 at Hogwarts. It's similar to what one experiences when solving a combinatorial MIP using branch-and-price (i.e. column generation) in practice. Starting with the root node, as you begin to apply restrictions and generate new columns, your LP objective function value usually drops*, and half-way through, your solver promises a really good solution. The possibilities are exciting. Alas, as your restrictions increase and you get close to the end state and your solution becomes increasingly integral, your objective function suffers a backlash from those nasty combinatorial constraints, and the objective function value goes through the roof. Invariably, much like a TV or book series, the ending is almost never quite as exciting as how one expects it would be. After investing all that time and effort. Perhaps, like life, good soaps are more about the journey and less about the destination.

*update (July 1, 2012)
The LP relaxation objective function value drops because:
a) the unrestricted subproblem in many large-scale planning problems is discrete, nonlinear, nonconvex; it is quite difficult to solve this problem to provable optimality within a reasonable amount of time

b) adding restrictions initially eliminates many bad solution areas, i.e. it simulates the role of inadvertent cutting planes, thereby improving solution quality.