Our final example of solving very large linear and integer programming problems comes from the airline industry. One major problem for airlines is the scheduling of their flight crews. As you all know, the airline industry is heavily unionized and there are very strict limitations on how to use a crew. For instance, there are rules on how many hours a day a crew is in the air, limits on the number of hours a crew can be away from their home base before they must layover in a hotel, and so on and so on. But crew expenses are the second largest operating expense an airline has (after gasoline). Therefore, there is an opportunity to work with a hard problem leveraged by enormous potential cost savings.
Consider the following example. Suppose an airline has three planes based in Atlanta (this is going to be an artificial example, of course). One plane goes between Atlanta and Miami with the following schedule:
A: Atl -- Mia 8:30-9:30
B: Mia -- Atl 10:00-11:00
C: Atl -- Mia 11:30-12:30
D: Mia -- Atl 1:00-2:00
E: Atl -- Mia 2:30-3:30
F: Mia -- Atl 4:00-5:00
(There are a million reasons this is not a realistic schedule for one plane, but I want to illustrate crew scheduling, not plane scheduling). The second plane flies between Atlanta and New York on the following schedule:
G: Atl -- N.Y. 9:30-11:30
H: N.Y. -- Atl 12:00-2:00
I: Atl -- N.Y. 2:30-4:30
J: N.Y. -- Atl 5:00-7:00
Finally, the third plane goes on a Atlanta, New York, Memphis, Atlanta trip as follows:
K: Atl -- N.Y. 9:00-11:00
L: N.Y -- Mem 11:30-12:30
M: Mem -- Atl 12:45-2:00
N: Atl -- N.Y. 2:30-4:30
O: N.Y. -- Mem 5:00-6:00
P: Mem -- Atl 6:15-7:30
Every flight leg needs to be covered by a crew based in Atlanta. For simplicity, we will assume that all crews must be returned to Atlanta each day. The labor contract is particularly simple. If a crew works (is away from Atlanta) up to four hours, they will be paid 75% of a base rate. Between 4 and 8 hours earns 100% of the base rate, and above that earns 200%. So, if a pilot earns $500 for an 8 hour day, she will be given $375 for a two hour day, and $1000 for a 10 hour day. Note that many contract restrictions have this highly nonlinear aspect: small changes drasticly increase the costs. How can we staff these flights in order to minimize costs?
First, let's define a few terms. An individual flight segment is called a leg. A combination of legs, beginning at Atlanta and returning to Atlanta is called a pairing. Each pairing will correspond to a possible schedule for a single flight crew. Here are a few possible pairings.
AB with cost .75
KLM with cost 1.00
KLMNOP with cost 2.00
A schedule is a set of pairings that covers all of the legs exactly once (or at least once if deadheading (flying without working) is allowed. Here are two schedules:
AB,CD,EF,GH,IJ,KLM,NOP for total cost 6.25
ABCDEF,GHIJ,KLMNOP for total cost 6.00
Is there a cheaper combination available? In order to be certain, we
would have to check all pairings. Let's suppose we could list all
pairings. We can let 
be 1 if we use pairing j. This leads to
the following integer program:
Minimize 
Subject to
for each leg i
where 
is 1 if leg i is served by pairing j.
This is an example of the set partition problem.
In general, though, it is not possible to list all the pairings. We would like to use something like variable generation but there are a number of difficulties. Here are a few:
-- the above is an integer program, not a linear program. Furthermore, rounding fractional solutions does not seem very bright. Dual values are therefore difficult to define.
-- contract rules make it very difficult to determine what the cost of a pairing is. Each pairing must be sent to what essentially is a black box. This means we have to check each pairing individually, rather than solve a single optimization problem to determine the best one.
-- the integer program is hard to solve and becomes impossible to solve if the number of generated pairings is too large.
One possibility is to create a series of much smaller problems as follows: begin with a schedule, though it might be a bad one. Arbitrarily choose two pairings. Generate all pairings using just those legs. Solve the resulting set covering problem. Repeat.
For instance, we might begin with
ABCDEF, GHIJ, KLMNOP
and select the first two pairings. The feasible pairings using ABCDEFGHIJ are
AB, CD, EF with cost .75
GH, IJ, CDIJ, GHEF with cost 1.00
ABCDEF, ABCDIJ, ABIJ, GHIJ with cost 2.00
(did I miss any?). I leave it as an exercise to write down the resulting set partion problem. One solution is AB, CDIJ, GHEF with cost 2.75. This is much better than the cost of 4 of our initial pairing so our current solution becomes AB, CDIJ, GHEF, KLMNOP with cost 4.75. We could continue by looking for a new pair, generating new pairings, and solving the resulting set partition problem.
This approach is right on the interface between variable generation and heuristic problem solving. Notice that no dual information is passed on to the variable generation phase. In fact, it is quite difficult to determine what reasonable dual values are.