Optimizing Shubh Laabh: Harmonious Profitability

Sustainable machine-generated, data-driven decisions
The growing popularity of 'Big Data' coupled with 'machine learning' techniques coincides with an increasing use of automated, machine-computed solutions for a a variety of business problems that were once solved and optimized based (predominantly) on human inputs. Machine-generated solutions have been shown to be superior to these previous methods on the measured performance metrics in many instances, and companies all over the globe have deployed advanced analytics and business optimization models (e.g. built using Operations Research) to achieve incremental profitability, cost reductions, or improved system efficiency. However, all is not well. Some solutions are sustainable, and work well over time, while others begin to run into a seemingly endless stream of human or environmental issues, and fall by the wayside. 

What differentiates sustainable machine-generated optimizations from the unsustainable ones? The answer is not straightforward, and this post explores one aspect. For an example of what kinds of issues can crop up, see this BBC news article: "Amazon workers face increased risk of mental illness", as well as this older article on 'unhappy truckers'. A portion of the BBC article highlighted below is color-coded to show where sustainable decision optimization could be potentially applied to improve upon the status-quo):

 "..... Amazon said the safety of its workers was its "number one priority."

Undercover reporter Adam Littler, 23, got an agency job at Amazon's Swansea warehouse. He took a hidden camera inside for BBC Panorama to record what happened on his shifts.

He was employed as a "picker", collecting orders from 800,000 sq ft of storage.

A handset told him what to collect and put on his trolley. It allotted him a set number of seconds to find each product and counted down. If he made a mistake the scanner beeped.

"We are machines, we are robots, we plug our scanner in, we're holding it, but we might as well be plugging it into ourselves", he said.

"We don't think for ourselves, maybe they don't trust us to think for ourselves as human beings, I don't know.

..... Prof Marmot, one of Britain's leading experts on stress at work, said the working conditions at the warehouse are "all the bad stuff at once".

He said: "The characteristics of this type of job, the evidence shows increased risk of mental illness and physical illness."

"There are always going to be menial jobs, but we can make them better or worse. And it seems to me the demands of efficiency at the cost of individual's health and wellbeing - it's got to be balanced." "

I spent the early-mid 2000s redesigning, and improving airline crew scheduling optimization systems. This period also happened to be the industry's most tumultuous: 9-11, out-of-control fuel and labor costs exacerbated by the invasion of Iraq, repeated strikes by various worker unions followed by contentious negotiations that lead to multiple CBAs (collective bargaining agreements) being ripped up and rewritten, and companies lining up to file for Chapter-11 bankruptcy protection, etc. Endless problems. The office atmosphere got quite intense when the R&D team somehow managed to find itself in the middle of these events, and facing heat from all sides (management, unions, soaring passenger complaints) on the kinds of solutions that were generated by our decision support systems (The US airline industry pioneered the use of such techniques). The analytical lessons empirically learnt from such episodes are hard to replicate in classrooms. One such lesson was "pay a lot of attention to the impact of your model on the people and environment". The application of this lesson has been explored in this space in a variety of contexts earlier: here (Gandhi's methods), here (Smart-Grid), here (Airline Crew scheduling), and here (Conflict resolution). The issue is revisited here by borrowing an idea from traditional Indian business philosophy to see if new insight can be generated toward answering our question on sustainable business optimization.

(pic link source: http://www.indiabazaar.co.uk)

(Updated: November 30, 2013 Finally found the link to article that inspired this post)
It is interesting to note that for centuries, traditional business communities in India had adopted the policy of Shubh Laabh (written in Hindi in the picture), which roughly translates into 'auspicious/harmonious profit' (Aravindan Neelakandan, co-author of 'Breaking India' in the linked article notes: "Lakshmi symbolizes the wealth that is holistic: it is wealth that puts welfare (Shub) before profit (Laabh)." The pursuit of wealth and profitability was never frowned upon in Hindu society, while unconstrained profit maximization was recognized as a socially destabilizing and ecologically unsustainable objective.  'Shubh Laabh' recognizes and respects the presence of long-lasting and latent side-effects that arise from business decisions (that can bring you 'bad luck') and attempts to balance them equitably with the more immediate goal of profitability (Laabh). These traditional businesses employed some operational form of Ahimsa (the principle of minimal harm) to optimize Shubh Laabh:

Rule a) limit harm (hard-constraint version)

Rule b) minimize harm (soft-constraint version)

Let us see how this idea can be incorporated within modern decision optimization systems. Amazon appears to have satisfied all legal requirements via (a) by making safety a top priority. It has probably ensured that the statistical rate of accidents is below some stringent threshold. In the airline world, (a) is achieved by ensuring total compliance with respect to all FAA- and CBA-mandated safety rules. However, this represents a necessary condition that tolerates a certain level of error as 'legally acceptable collateral damage'. The resultant formulation is: maximize profitability subject to safety regulations. However, this in itself is an insufficient specification if we want our algorithms to minimize harmful side-effects. An Ahimsa-based model would additionally consider (b) and eschew profit achieved at the cost of a reduced employee quality-of-work-life (QWL) or environmental degradation, as unsustainable and counterproductive in the long run. 

For large-scale systems such as a retail supply-chain or airline crew schedules, a reasonably skilled analytics professional should be able to incorporate requirements (a)-(b) within their decision support algorithm which, among alternative near-optimal solutions (and there are often many of these), selects one that also maximizes worker QWL, and/or minimizes harm (e.g. reduces carbon footprint). This requires the human-and-environment-variables in the system be treated positively as an active and equal partner based on mutual respect, by explicitly including their requirements as part of the primary goal (objective function), going beyond a legalistic/adversarial approach of treating these variables as a 'loss-making noise that has to be managed' by specifying a minimum tolerance constraint.

To summarize
It is possible to achieve sustainable profitable solutions via automated decision support systems that are also harmonious and sustainable, by paying due respect to all the stakeholders (including Ms. Nature), right from the design phase.

An old blog discussed Rajiv Malhotra's use of 'mutual respect' (as opposed to mere tolerance) as a simple but powerful basis for two heterogeneous groups of people, or people subscribing to conflicting thought systems, to achieve a fair and sustainable equilibrium in their interactions. It appears that such a mutual respect:

a) is implicitly present in the idea of Shubh Laabh, which in turn

b) can be employed as a key guiding principle of 'sustainable design' when building decision support algorithms for managing complex business problems, where multiple, and potentially conflicting, goals have to be delicately balanced.

The opinions expressed in this article are personal.

Operations Research for the SmartGrid - 1

A popular joke in my undergrad campus at IIT-Madras used to be "why is the large water tank in our campus not used? Answer: the design engineers did not take the weight of water into account". The legend may be as real as the croc in the campus lake, but newspaper reports a few days ago quoted a US government spokesperson saying that the 'heath insurance website worked correctly, but just did not take the volume into account'. I'm sure a lot more attention was paid to the voters within the sophisticated analytical models used during the 2012 elections. Volume was not a problem then, somehow. Actions reflect priorities, as Gandhi said. So what are the priority areas in Smart-Grid research?

I recently attended the IEEE SmartGridComm 2013 international conference in the beautiful city of Vancouver, Canada. (A very brief historical tangent: From my Indian-American immigrant perspective, Vancouver is also a somber reminder of the discrimination that was once practiced by the US and Canadian governments, exemplified by the Komagata Maru incident). The paper presentations were refereed entries, uniformly of high quality, and largely focused on the dizzying science and technology associated with the various elements of the smart-grid (electric vehicles, batteries, wind, solar, communications, security, ...). Marry this with 'Big Data' and you get the convoluted buzz of two 'hyperbolic' distributions. Personally speaking, the glaring problem was this: the tech part felt overcooked, and the human part, somewhat overlooked, save for this five-minute talk, and the excellent keynote talks, which emphasized the latter (a favorite keynote comment described the important and immediate practical problem of 'transmission optimization' as the drunken uncle of the smart grid - largely ignored, but full of smart ideas). I found that several others at the conference too shared an opinion: the single most important component of the Smart-Grid remains the people for whom it is being built in the first place. If anything, understanding their behavior and impact is more important than ever before.

The world of electrical system modeling is full of elegant math that manage electrons that flow through circuits obediently as dictated by the equations. These models match up relatively well with reality (even imaginary numbers work here). In contrast, real world ORMS projects usually begin with people's real and changing requirements, and culminates in finding lasting solutions for real people, using noisy and incomplete SmallData. Unlike widgets, packets, and electrons, the goal of accurately modeling human response largely remains an open challenge, and the temptation to simply ignore this component of the SmartGrid is strong. However, the empirical, perhaps paradoxical, lesson I've learned the hard way is that the more effectively we want to mechanize, automate, and optimize systems by reducing or eliminating manual intervention (i.e. save humans from humans, a la Asimov's robots), the more practically important it becomes for our optimization models to take into account the behavior of, and the implications for all the human stakeholders, upfront. Be it workforce scheduling, Big data analytics, or the SmartGrid, an ahimsa-based multi-objective approach that also minimizes harm or maximizes benefit to the human element and blends harmoniously with the environment is likely to be more sustainable. Which is another way of saying: SmartGrid is one heck of an OR opportunity and I'm glad to be a small part of this journey.

The next part of this series will review some interesting SmartGrid optimization problems.

Optimizing Schedules: QWL Considerations

A first blog post from India.
Impact of Decision Variables on Humans
This practice related comment was triggered by yet another useful 'Punk Rock OR' post  - on 'optimization and unhappy truckers', which briefly reviews a Tom Vanderbilt article that noted that mathematical optimization may having contributed to the incremental unhappiness of employees who were affected by the decisions prescribed by the model. TV's article also talks about the optimization of airline crew schedules, which is a useful example to analyze some of the side-effects of optimization.

Scheduling Objectives

The rules that govern the safe scheduling of airline crews are incredibly complex, and used to appear in a bound book form (every single one must be programmed into the optimization system, scarring an Operations Researcher for life). Additionally, there are hundreds of different 'cost' components that typically go into an airline crew scheduling system that is so neatly abstracted to "Min cx. Ax=1, x binary" in OR textbooks. Some of the objectives are listed below:

1. cost, utilization, efficiency

2. quality of work life (QWL)

3. schedule regularity

4. operational resilience

5. Downstream system compatibility

.. and many more..

Among these, a component that is most relevant to the discussion here is QWL, a non-negotiable component of "soft rules" that go beyond what the FAA prescribes and diligently adheres to the letter and spirit of a collective bargaining agreement (CBA) between the management and representatives of the crews. QWL metrics are audited and checked before schedules are published, and tracked over time. A drop in QWL metrics can result in followup phone calls from crew representatives, and keeping the call volume (and decibel) to a minimum is a clear and track-able goal.

Anonymous Schedules, Personal Impacts

While traveling on company flights, I initially used to strike up a conversation with flight-attendants (FAs) to get their opinions on their schedules, and any particular issues they had. There were some harsh complaints, but also the occasional compliment based on their feedback that compared their QWL to FAs in other carriers.  Nevertheless, schedules are initially anonymous, and thus indifferent to personal needs, while also being free of privacy concerns. It is safe to say that unless schedules are personalized, there's bound to be unhappy crews. Personalization is at odds with automation, and the task of optimally synchronizing and scheduling 30, 000 FAs and pilots, and hundreds of expensive aircraft that operate thousands of flights per day, while trying to keep costs down, reliability high, and crews happy is non-trivial. Luckily, the space of feasible schedules contains many trillions of possibilities, and is diverse enough to accommodate many, many management and crew objectives to produce tons of alternative near-optimal solutions. In fact, this feature plays a vital part in designing new and improved crew safety rules during CBA negotiations. To summarize, modern, large-scale industrial optimization systems are sophisticated, robust, and flexible enough to accommodate a myriad of human-impact objectives without breaking a sweat. Who knows, truly personalized schedules that sync with personal calendars, while also keeping utilization high, may well be technically feasible now. Preferential bidding systems (PBS) have already been in place for more than a decade now.

Actions Reflect Priorities

Some of my purely personal observations based on the data I have seen: the QWL metrics for a schedule is correlated to the negotiating clout of the organization for whom the scheduling is done, and the importance given by management to maintaining harmonious relations with them. Higher up the food chain, the better the QWL. Not surprisingly, some employee organizations may have their own optimization systems that enable them to evaluate their schedules (and also 'game' the system). 

In between the scheduler and the 'schedulee' is the OR layer, the secret sauce. I'd like to believe that OR'ers can make and have made a positive difference by paying attention to the net human impact of a binary variable changing from a 0 to 1 to find win-win stakeholder-friendly alternative optima. I've seen analysts devote many days trying to figure out how to make excruciatingly complex experimental QWL constraints work cost-effectively in the optimization system to break an ongoing CBA negotiation deadlock: for example, how to limit the flying done by west-coast based pilots when it is dawn, Eastern Standard Time (EST). Putting the plane on autopilot and going to sleep is not an option. I have even seen prototypes that used "crew happiness variables" :)

It is interesting to look at the optimized crew-aircraft schedules for fractional jets that ferry well-heeled folks and time-starved execs on Gulfstream-Vs to various parts of the world between tiny airports. Needless to say, non-bottomline 'costs' and degree of personalization play a prominent role in the objective function. The customer is both king and queen. In the end, a well-designed optimization system's objectives can accommodate the considerations of all the stakeholders to consistently (and merely) reflect their relative importance from a human decision-maker's perspective. Nothing more, nothing less. As Gandhi ji said, actions reflect priorities.

Are Operations Researchers Eulerian Decision Makers?

It is interesting to read Venkatesh Rao's book 'Tempo' (and the blog) from an Operations Research (OR) perspective and explore its ideas on human decision making. To better comprehend the themes in the book, I've been trying to map the examples in the book to familiar OR-type problems. For example, timing the purchase of consumer products at Amazon.com over a period of time while also managing to satisfy the free-shipping threshold to the extent possible feels like playing a game of tetris where we try to optimally delay the inevitable ("entropic optimization").

A recent tempo blog post compares Lagrangian versus Eulerian decision makers (let's call them LDMs and EDMs). These two approaches appear to have their origin as choices of frames of reference for studying fluid flow. An LDM tracks a single 'parcel' of flow though its entire journey while the EDM examines many parcels that flow through a particular location. Let's apply this to an airline OR (crew scheduling) scenario:

an LDM follows a particular crew operating a sequence of flights through a network before returning to her/his base, while the EDM looks at many crews arriving and departing through a particular airport. LDMs track flow-paths, while EDMS zoom in on activities within a specific node in the network. Another example from airline network revenue optimization: an LDM may focus on a passenger flowing and the accumulated revenue through an itinerary consisting of multiple flights, whereas the EDM zooms in on the variable price and fixed cost associated with a seat on a specific flight that is a part of many passenger itineraries.

Intuitively, it feels as if the LDMs focus on the clearly visible primal decision variables, whereas the EDM focuses on the latent, underlying dual problem. Column generation as an iterative optimization approach works well when the EDMs compute and transmit useful 'dual' signals from specific locations to LDMs (e.g., the rate of pilots arrive and depart at their node) who in turn, collect and apply this updated information to stitch together new and improved flow-paths across the network (i.e., columns), which in turn ensures more balanced and smoother flows across the nodes (i.e., rows). For some problem classes, if we solve the dual problem, our primal decisions are also at hand, and if the dual is unsolvable, the primal is likely to be problematic as well. Conjecture: Lagrangian and Eulerian decision makers build mental models that represent (informal) primal and dual formulations of the same problem. Depending on the context, one or the other approach may be more convenient or effective. 

The ability to extract information from noisy dual signals is useful in solving complex or large-scale industrial optimization problems. For example, in the airline revenue optimization example, it is known to be more convenient and reliable for airline revenue/scheduling planners to take decisions based on the shadow prices of flights, rather than rely on the optimized prices of the millions of possible itineraries. Dual methods are insightful and can help solve a decision problem where a frontal assault fails. To the best of my knowledge, the default out-of-box method invoked by the leading mathematical optimization software packages today for solving linear programs is their dual algorithm.

In general, Eulerian decision making or as this post sees it, 'dual-driven decision making' may be the more attractive first-choice approach for human decision making. The tempo blog notes:
"... When flow gets turbulent, the fluid mixes a lot. To properly follow a “parcel”, you have to let it expand as flow lines diverge and churn. This means there is more fluid in your parcel than you started with, more “noise.” Eventually you are trying to analyze world hunger — the entire body of fluid.
But the Eulerian static parcel stays the same size. It just bleeds causal structure and gets more entropic. The action gets a lot more random and choppy, but still tractable in size. It is also easier to shrink what you’re paying attention to when things get complex — it’s called focusing – than it is to reduce the ambition of a model you’re tracking (generally called pruning)..."

Are Operations Researchers Eulerian Decision Makers?

Guesstimation in Optimization and Analytics

Guesstimation
Browsing through the various examples examined in the 2008 book 'Guesstimation', it is apparent that the basic ideas behind this approach of "solving the world's problems on the back of a paper napkin" are useful for analyzing real-life optimization and analytics instances. Whether we are looking at (i) Smart-grid optimization ("how many hours does it take to charge an electric car"), or (ii) Hazmat routing ("what is the risk of dying per unit mile of road") or (iii) environmental problems ("how much farmland will it take to convert all gasoline cars to ethanol"), guesstimating values can be critical to effective model formulation in the absence of precise information. Guesstimation is a 'small data' method that can improve the effectiveness and performance of our 'big data' analytics.

Optimization
Let's look at an 'elastic' linear programming formulation:
LP: Minimize c.x + P.s
A.x - s <= b
l <= x <= u, s >= 0
where we've added artificial variables 's' to ensure feasibility of LP for any bound feasible 'x'. Often times, exact values for b, c, l, u, or portions of A are not available. Furthermore, we allow artificial variables to be active at some high but as yet unknown penalty rate of 'P'. We often end up guesstimating these values in industrial applications since many of these values are not known accurately.

Example (i) in the previous paragraph gives us a charge rate per car (a component of 'A' matrix). if 'x' is the number of cars to be charged, and 'b' is an upper bound on the time available and 'c' the cost of electricity for that duration, we can predict the 'ballpark' cost incurred and the charge stored. Similarly, example (ii) gives us the average risk per unit mile as a cost coefficient 'c'. By extending this calculation to denote high and low risk arcs in a network, we have an initial minimum risk network path optimization formulation at hand. Finally, example (iii) gives us an unconstrained resource requirement. This value allows us to quickly assess the impact of adding a resource constraint.

Thou shalt always Guesstimate!
Direct uses of guesstimation in practical optimization include the calculation of tighter bounds (l, u) for decision variables, and the smallest valid values for the big-M numbers that riddle integer programming formulations. If we think of (u - l) as a measure of our ignorance about the as yet unknown optimal 'x', guesstimating tight bounds is akin to maximally reducing its "prior variance". While guesstimation in the book is done using feasibility calculations, we can and should incorporate optimality considerations to obtain sharper bounds for such unknown variables. Using solver default (0, infinity) values is lazy and bad practice. Also, spending some time to improve bounds often gives us insight into the nature of the optimal solution, and which constraints are likely to be more restrictive, and helps catch modeling bugs earlier.

Example 1: what is the cost of not scheduling a crew for an airline flight?
In airline crew scheduling, the flights in a schedule are partitioned among crew pairings (see this post for a problem description). Every flight must be covered by exactly one pairing. This is a hard constraint, but in practice, we have to temporarily employ its elastic form of the type described above, and penalize violations via 'P'. How do we determine an appropriate penalty value? This would be the cost of leaving a flight uncovered. Such flights have to be covered by a reserve crew, which comes at a certain cost that can be calculated and is typically smaller than some default value we may have otherwise chosen. The dual variable value associated with an uncovered flight in an optimal LP solution attains a value close to 'P'. Any new column (x(j)) generated that covers this flight will subsequently will have a reduced cost of order (c(j)-P), and so on. Good guesstimation of P helps in producing manageable reduced costs, and accelerates algorithm convergence.

Example 2: what is the price elasticity of point-and-shoot digital cameras?
Price elasticity is a dimensionless (negative) quantity that gives us the expected percentage change in sales for a percentage change in price. We can expect that this value will be more than that for electricity, grocery, and dairy items, which are essential items that people are less willing to give up when price is hiked, and are likely to be inelastic (less than a percent drop in sales for a percent increase in price, say -0.5). The value will be lower than that of highly discretionary purchases like fashion apparel or leisure airline tickets (which have an elasticity of -4 to -2). The geometric and arithmetic mean of 3.0 and 0.5 gives us a range (-1.8, -1.2). A data-driven estimation of this value should be compared against this guesstimate as a sanity check. For example, if regression models on a data sample estimates an 'optimized' elasticity parameter value of -5 or -0.1, we may want to double check our modeling, or run the risk of producing wild predictions.

Another use of guesstimation is in generating plausible random optimization instances to demonstrate the effectiveness of new NP-Hard algorithms for a certain problem class if only limited real-life data is available. It can help weed out weird and contrived instances that skew the degree of difficulty of the problem and make it seem much harder than it actually is in reality.

Synchronized Scheduling Case Study - Part 3

The case study is introduced here.
The ICAR goal is derived here.

Model
The ICAR problem can be specified as follows:
Find a set of feasible crew pairings and aircraft strings such that:
a. every flight in the LEG schedule is covered exactly once by an aircraft string

b. every flight in the LEG schedule is covered exactly once by a crew pairing

c. any string and pairing is used no more than once (let's denote the non-zero pairings and strings as 'active')

d. the total cost is minimized

e. if an active crew pairing contains a connection t(i→j) in T, and there is also some active aircraft string that also contains t, then we say that the crew turns with the aircraft and is thus synchronized. Downstream systems can ensure that the actual crew assigned to flights i and j remain with the actual aircraft tail number that flies i and then j.

f. Maximally satisfy a reliability measure that is proportional to the tightness and the number of the synchronized connections in T. For the purpose of illustration in this post, we specify that a certain minimum count (m) of the connections in T be synchronized. The aim here is to be smart about picking the right airports and connections to synchronize to boost reliability as well as utilization.

g. The active strings belonging to a sub-fleet should form a Hamiltonian circuit. This is a maintenance requirement that tries to ensure equal wear-and-tear across the fleet. There are other constraints that are also interesting topics in their own right, but we'll ignore them here for brevity.

Resource Synchronization Modeling
Our main focus here is on requirement (f). We provide some sample approaches to handling synchronization in large-scale scheduling:
a) Within the subproblem: 
Really tight day-connections t in T can be directly enforced by restricting t to be the only valid connection out of i and into j (i→j) in the flight network. Thus any pairing or string that comes of the subproblem that covers flight i will subsequently cover j. However, we cannot apply this  idea to all connections in T since that is likely to be overly restrictive. 

b) Within the Master program: 
Let p(t)  = sum of all pairing variables that contain connection t
q(t)  = sum of all string variables that contain connection t
Note that p and q will be no more than 1.0. We can impose the following synchronization constraint: 
∑_T p(t)q(t) ≥ m 



The bilinear terms in the reliability constraint can be linearized in a straightforward manner. A personal favorite is the reformulation-linearization technique (RLT). z(t) ≡ p(t)q(t) ⇒

∑_T z(t) ≥ m, z(t) ≤ p(t), z(t) ≤ q(t), z(t) ≥ p(t) + q(t) - 1

Thus, by adding O(T) very sparse constraints and continuous variables z, we can model the synchronization component of ICAR without requiring any approximation, and the resulting formulation remains tractable. The RLT can be applied in a similar manner to synchronize three or more resources as well. The keys for this 'frontal assault' to work are:
1. The cardinality of set T be manageable in the context of the application.
2. Synchronizing two resources is easier than juggling three or more. We can see from the synchronization constraint that if the p-variables are fixed, the z-variables can be eliminated, leaving us with just the q-variables. This 'two variable per constraint' structure makes life much easier during column generation. The synchronization duals associated with the connections in T tend to work much more effectively in generating string-pairing pairs that cover a beneficial subset of common turns in T.

Epilogue

The ICAR solutions that were actually implemented (different from the illustrative version presented here) significantly improved upon the existing approach. It reduced business cycle time, greatly increased reliability, and reduced costs. The success of the ideas employed to tackle ICAR spurred the development of new, algorithmic techniques to solve the next-generation integrated crew scheduling problems that went on to save the LEG carrier many million bottom-line dollars annually during some difficult economic times. As far as the competition with LCA was concerned (for which this solution was designed): LEG had incurred enough losses and pulled the plug. Operations Research successful, patient dead.

Synchronized Scheduling Case Study - Part 1

Synopsis 
When a low-cost airline (LCA) entered a short-haul aviation market many, many years ago, a legacy airline carrier (LEG) decided to compete with LCA on its own turf by matching the LCA's fare, frequency and super-quick aircraft turn-around times on ground ('turns' for short). This required a high degree of coordination between LEG's in-flight crews (pilots and flight-attendants), ground-crew, airplane maintenance planners, and the airline schedulers (including their scheduling optimization system). In particular, the utilization of the pilots and the flight-attendants had to be maximized. The challenge however was that all these different resources were part of separate organizational structures and were governed by different contractual rules, and the LEG idea eventually turned out to be cost-prohibitive and unreliable due to poor synchronization of resources.  On the other hand, the Operations Research (O. R) team built a specialized scheduling system for LEG (far ahead of the literature available at that time) that would've achieved the needful. Unfortunately, the silo-ed organizational structure hindered adoption.  Result:  Unlike the legendary revenue optimization contest where the legacy carrier triumphed, the tables were turned here, and the LCA flourished. The low-cost LEG idea was resuscitated many years later in a different context and market, and did a better job using the lessons learned from this early setback. In the next few posts, we will compare the two approaches used to synchronize these resource scheduling tasks and summarize the lessons learned.

Airline Scheduling Basics
Given an aircraft schedule, the resource planning is done sequentially in order of their profitability (or cost) to the airline. Thus:
LEG flight schedule → pilot schedule→ flight attendant schedule → aircraft maintenance routing

The cost-critical task here is the construction of "pairings" (or "strings" for aircraft), which denote partial (unassigned) solutions that represents partial tours of a resource. For LEG pilots (set of two persons), and FAs (set of three persons), this represents a tour in a time-space network that starts from a crew domicile (a small subset of airports in the LAC schedule), traverses a bunch of different airports over 1-5 duty days with intervening periods of rest known as layovers, before returning to the home domicile, while satisfying a myriad of contractual and FAA rules for work hours, rest time, etc. In short, the cost and constraints that determine each pairing is an extremely complicated nonlinear, non-smooth, non-convex, nonplussing mixture of on-duty + rest + reliability + crew work life balance + other path-dependent factors. 

Good quality pairings can be created using a dynamic column-generation procedure. A column here represents a pairing, and during an optimization run, thousands of pairings are generated and selected from among the many trillions of possibilities using a "branch and price" scheme. Eventually a subset of the generated columns are selected such that every flight in the time-space network is covered by exactly one pairing, and such that the total cost is minimized (where the actual 'cost' being optimized is a combination of a hundred-odd objective function components).

Note: An airline crew-pairing solver's set partitioning problem is arguably the easiest optimization model in the world to represent on paper:
{SPP: Minimize cx : Ax = 1, x binary, x ∈ X}

In contrast, the real-life computer code used to manage this simple model can easily run in the order of many hundred thousand lines (largely due to the complicated and detailed nature of X), with expensive parallel-processing machines, and an embarrassment of CPLEX licenses to match. Why? A small percentage point reduction in crew pairing cost (cx) can easily recover all these infrastructure costs and then some. Since crews get paid the max of planned and actual costs, these numbers are actual bottom-line savings. Furthermore, such scheduling tools can be mission-critical systems that run 365 days a year, requiring O.R product support staff to be on call like primary care doctors. 

Solution Approach
Downstream systems, and not of immediate interest to this post, combine these pairings into actual monthly schedules with pilot, first officer, and flight attendants assigned by solving yet another set-partitioning problem. Thus cost-effectively scheduling even a single resource requires a sophisticated solution approach. In those days, academic literature often contained interesting approaches that looked good on paper but proved to non-implementable because of the highly context-driven and data-driven nature of this problem that requires developers to pay careful attention to problem size, exploit special structures in SPP and X, and keep in mind certain carrier-specific objectives. On the other hand, interested readers can refer to this journal paper - the first one I read on the job. It is also the #1 cited INFORMS paper based on a recent ranking. Today, this portion of airline planning is typically outsourced to specialized airline crew-scheduling software vendors.

Pairings and Strings
A set of pilot pairings tell you, for any given LEG flight: the in-bound flight that the pilots arrived in, and the out-bound flight on which they will depart. Of course, if a LEG flight schedule is built with lots of tight turns (say 30 minutes or less) at an airport, then it makes sense from the point of view of operational reliability and cost, for the crews to stay with, and depart on the same airplane, assuming of course, that the aircraft routers will assign the same aircraft (tail number) to these flights. This is a resource synchronization rule: Keep crews and aircraft together to the extent possible while also keeping costs low and satisfying all contractual duty, rest, and maintenance rules.

The FA scheduling system can take pilot pairings as inputs to try and keep the FAs with the pilots. Unfortunately, since these crews have different operating hours and safety rules give the varying nature of their job descriptions, very often, pilots and FAs have to break up and depart on different flights. This is an operational nightmare when you are trying to work with tight turns to compete with LCA, and actual costs shoot up if you 'over-synchronize'. To make matters worse, the strings (partial aircraft maintenance routing solutions) also have to be tightly woven with crew pairings. It's a planners nightmare.  Believe it or not, LEG folks actually built much of these schedules separately ("legacy approach"), with each scheduler anticipating what the other person will do, often coordinating via phone-calls in this multi-person game. Result: an expensive and sometimes operationally brittle schedule that increased operational costs and ate up some customer goodwill, which eventually resulted in the plug being pulled. In the next part, we'll see how LEG's OR team analyzed this problem.

to be continued .....