Synchronized Scheduling Case Study - Part 2

The case study was introduced in the previous post. Read the introduction here.

.... Despite their suboptimal approach, the schedulers of the LEG carrier did some nice work with their synchronization approach.

2SAT versus 3SAT
There is a jump in decision complexity when moving from a two-body conflict resolution problem to three-body conflict-resolution. Intuitively, we can observe this in linear programming (LP) problems. LPs limited to two variables per constraint are easier to solve. The dual (two constraints per variable) is a generalized network flow problem that can be solved using purely combinatorial methods. Intuitively, one can adopt an alternating heuristic that iteratively fixes one variable and optimizes the resulting univariate problem. In computational complexity theory, SAT-2 is easier to manage compared to SAT-3.

Rather than trying to simultaneously juggle flight attendant (FA), pilot, and aircraft maintenance schedules, the LEG schedulers adopted an simplification. They combined the two human elements into a single 'crew' scheduling entity. This can be achieved via "co-pairing", i.e., by building common pairings (partial schedules) for FAs and pilots employing X = {X_PILOT ∪ X_FA}, i.e., every pairing would be feasible to both pilot and FA contracts and FAA regulations. Column generation allows you incredible flexibility in accommodating such a change. This flexibility is invaluable when hit by a perfect storm. Now, they could work with a two-variable per constraint structure so that their telephonic "alternating heuristic" negotiations could converge in a timely manner. Unfortunately, such a beneficial reduction in complexity was accompanied by inefficiency. The approach erred inordinately on the conservative side. The resources were now too tightly integrated, resulting in a cost spike due to under-utilization of expensive resources. LEG's R&D team was invited to resolve this problem.

Integrated Crew and Aircraft Routing (ICAR)
The OR team quite naturally proposed an integrated scheduling approach that would reduce costs, improve reliability of operations, and also enable tactical synchronization of flight connections. However, the number of possible connections to be evaluated is O(n²) for a n-flight schedule. Methods in the literature are typically data-agnostic; sophisticated alternatives to the straightforward approach designed to perform an acceptable job even in the worst case. Luckily, LEG's OR team had to solve only LEG's problem and not that of every future airline and space shuttle.

The Beauty and the Brute Force
Given the problem size spread over a five-day period, there are a few million candidates to synchronize in the theoretical worst case. However, our focus is only on same and overnight connections, which reduces the candidate list to a few hundred thousand. When we recognize that we only have to focus on the set T of connections of the same sub-fleet type at the same airport (duh), and exploiting a few other contextual restrictions, this final number is data-driven. It turned out that there were no more than tens of thousands of synchronization possibilities to deal with, 99% less than the theoretical bound. This finding allowed the possibility of cheerfully discarding (as we found out a couple of years later when some of the first journal papers on ICAR came out) all the neat out-flanking theorems and approximations presented in the literature.  The method chosen may score low on aesthetics but was effective and flexible in managing the full blown ICAR instances in context. There is a childlike joy in discovering that enumeration solves your practical business problem - akin to finding out that this emperor has very little clothes. This basic counting step gave the team a clear goal.

Problem Statement (at last)
Given a flight schedule, jointly construct feasible crew pairings and aircraft strings such that their scheduling intersection (elements within the connection set T) are optimally synchronized.

And, yes, there were a few TSP (Traveling Salesman Problem) instances to be managed within ICAR. To be continued....

Review of WVLPSolver: A Java-based Linear Programming Library

Pure Java based optimization tools released under benign licenses are popular in decision-analytics embedded industrial applications. They reduce maintenance efforts and deployment costs, keeping IT managers, analytical support engineers, and developers happy. No platform-specific issues to deal with. No license and patent infringement headaches.... It's a win-win for everybody, provided these 'free' analytical tools withstand the rigors of a production environment.

Recap: This tab summarized a set of pure Java tools a while ago here, talked about a DIY Java solver here that gets you to within a factor of 10-20 of CPLEX on combinatorial LPs, and chatted about "GooPLEX v1.0" some years ago here.

The new WVLPSolver library is introduced here (courtesy:  Bharath Krishnan, data scientist at CQuotient). This new solver is worth a look because its v1.0 appears to be more well thought out compared to the initial version of 'Gooplex'. In particular, WVLPSolver seems to employ a revised simplex scheme that would allow it to work with a minimal simplex tableau (see an old but remarkable (if extreme) illustration of this advantage). Per the introductory post, it employs the reliable Colt library, and is released under the Apache license. These three factors alone may allow this tool to become a useful workhorse in specific situations ("think small"). Great work by the developers, and hope they continue to improve upon this initial release.

Big Data produces a variety of decision problems (recent post related to this topic). In some situations, and depending on the problem structure, you may end up needing to solve tons of small but independent optimization problems, and in other cases, relatively fewer giant monoliths where a considerable amount of sophistication is required to produce consistently good answers. In the former case, an IT manager has to decide whether he needs to budget for a million-instance licensed version of an industrial-strength solver that works cross-platform, or hack-a-heuristic that generates "user-optimal solutions" but may end up confusing users, or go with a nice, pure Java LP brew. Each option has its advantages and disadvantages depending on the context. For analytics start-ups that offer solutions having a relatively small OR footprint, the last option may sound appealing.

The Gaussian Hare, the Laplacian Tortoise, and Big Data

Alternative Optimal Solutions
A recurrent theme of this tab is to highlight an important contribution of O.R decision modeling: alerting us to the presence of alternative optimal solutions (AOS). Prior posts relating to AOS can be found here and here.

Customers unfamiliar or uncomfortable with the jagged-edged linear programming (LP) models often seek refuge within the smooth world of classical calculus (a world now known to have been initially crafted by Kerala mathematicians, but i digress). Here, alpine slopes of gracefully changing functions invariably allow you to rapidly ski down to a uniquely best solution. Like the truism "Football is a simple game; 22 men chase a ball for 90 minutes and at the end, the Germans win", an applied math legend is that the Gaussian hare invariably trumps the Laplacian tortoise. Unless of course, modern day optimization solvers and decision science come into play and allow Laplace to overcome the various complications posed by non-smoothness. (Image below linked from http://www.econ.uiuc.edu)

Degeneracy
Well specified decision models in a variety of industrial situations admit plenty of good quality answers, so the problem is usually one of having 'too many' rather than too few options (my favorite academic researchers tackle increasingly difficult unsolved problems, whereas my favorite OR practitioners compete on identifying the easiest unsolved problems). A fundamental thumb-rule of practical decision optimization modeling is to advantageously exploit and defuse this often-deadly problem of 'degeneracy' that characterizes practical LP formulations, and a reasonably skilled analyst can turn a potential numerical liability of the LP model into a business analytical asset as follows.

AOS often hide in plain sight
The presence of alternative answers forces us to revisit our translation of business rules into an LP and devote some time toward gainfully analyzing the differences in the potential business impact of these seemingly equal solutions. The customer can use this feedback to re-examine and further refine his/her business goals and priorities. This process of iteratively improving the design specification provides valuable insight to customers, and helps setup a richer, and a more practical and robust optimization model.  Not that a similar exercise is impossible to accomplish using smooth approximations - just that the flexibility afforded by an LP model is often superior, and the tool kits for analyzing LP solutions have gotten amazingly better over the years. 

Means and Ends
It just doesn't make sense to crunch through 21st century "Big Data" analytics using bleeding edge data mining, econometric, and machine learning methods on the one hand, and on the other hand, downgrade to 19th century techniques, or random black-box methods to manage the underlying decision optimization problems and produce severely suboptimal and non-robust solutions. Using such shortcuts because "a quick one-iteration improvement is all that is needed" brings along with some risky side effects and potentially leaves a big chunk of 'Big-Data' value on the table. Do everybody a favor and upgrade to a Laplacian tortoise (e.g. CPLEX) and you will be surprised to see how fast it runs, especially on Big Data.

The amazing computational world of DIY Simplex

Operations Research students seldom get to look into details of sophisticated implementations of a sparse simplex solver for linear programming. The same is true for O.R practice where your focus is how best to use such tools. But if you work for a setup that cannot afford the steep royalty you have to pay for such tools, you can build your own in a few months. Its more likely to be about 100 times slower than Gurobi or CPLEX on large problems. If your LPs are small sized (less than 50,000 rows), it may do a decent job, but hey, the experience is quite amazing, and I highly recommend it. For one, the system of linear equations that you solved since high school will never seem the same. And you can read a couple of important journal papers authored by Suhl and Suhl (i kid you not). The dual method is the best default choice. If you have starting trouble, trying using 'Gooplex', google's first draft LP solver. Its a toy solver, but the code implementation looks professional and is a good starting point.

On the other hand, there's always COIN-OR, the good quality open source repository.

Google releases open-source Simplex Solver

good news for O.R practitioners. I wish COIN-OR would make their license as friendly as google's simplex solver. We'll have to look into the code to see if it's an efficient and effective implementation (e.g., dual simplex with LU factorization) for large LPs.


Here's the license details cut-and-pasted from the source.

1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */

Gurobi v/s CPLEX: A real-life LP example

The general availability of Gurobi, the new solver in town means that it allows us to compare how the de-facto commercial standard for the last 3 decades matches up. For starters, lets look at that good old work-horse, the Simplex Method. In particular, we will look at the dual simplex performance on a particular LP from real-life that has very few rows and many, many bounded columns that tries to maximize a linear objective function subject to "<=" constraints. Perfect for dual simplex since most of your work is with 6x6 linear systems for this instance.

Let's see what the default solvers of CPLEX and Gurobi do with it. You would like to think that there should not be much difference when it comes to 'mature' technology. Surprise.
These are run on my personal Ubuntu-Linux quad-core PC, 4GB RAM in serial mode. While the data is not available for public use, it should be easy to generate random instances of similarly sized LPs and do your own tests.

The result:CPLEX-dual simplex is nearly 40X slower on this instance.

--------------------------------------------------------
Problem stats: 6 Rows, 935645 Columns, 3192263 Non zeros

Gurobi solves it in 76 iterations and 10.16 seconds
Optimal objective 9.531245720e+05


CPLEX
-----
Tried aggregator 1 time.
LP Presolve eliminated 0 rows and 392 columns.
Reduced LP has 6 rows, 935253 columns, and 3191065 nonzeros.
Presolve time = 3.06 sec.

Initializing dual steep norms . . .

Iteration log . . .
Iteration: 1 Dual objective = 1203067.101646
....
Solution status = Optimal
Solution value = 953124.5720420766
Solution time = 391.32 seconds

It is well known that f your dual-simplex implementation is fast, all your branch-and-cut operations that rely on dual-simplex will also be that much more faster.

CPLEX-Primal was even slower, but CPLEX-Barrier does it in about 100 seconds (including the cross-over to a corner solution), which is still 10X slower. I tried many other tweaks with CPLEX for what should have been a relatively quick and simple problem to solve for an industry-standard LP solver, but without much improvement. To be fair to CPLEX, which is still a fantastic product, this is just one instance. Without the barrier solver as yet, Gurobi may be slower on LPs that are strongly amenable to interior point methods (more on that in a future post).

Hopefully, the owners of these products will continue to devote R&D effort toward these two great products and keep pushing the envelope, so we practitioners get the best of both worlds!

-------------------------------------------------------------------------------
Disclaimer: These are purely my personal observations made in an unofficial capacity, based on tests on a very limited sample of real-life data sets, and do not reflect the views of my employers or associates. I am not affiliated with Gurobi or ILOG-IBM.
-------------------------------------------------------------------------------