Case Study 6: Large-Scale LP/IP

Airline Crew Scheduling via Column Generation

ISYE 671 — Linear Optimization and Network Flows

Background

MidwestAir is a regional airline operating a hub-and-spoke network centered at Chicago O’Hare (ORD). The airline operates 40 daily flight legs across 6 spoke cities in the upper Midwest. Each flight leg requires a crew (a captain and first officer operating as a unit). MidwestAir needs to construct crew pairings — sequences of flight legs that begin and end at the crew base (ORD) within a single duty day — such that every flight leg is covered by exactly one pairing, while minimizing total crew cost.

This is a classic set covering problem that, in its natural formulation, has a very large number of variables (one per feasible pairing). You will use column generation to solve the LP relaxation efficiently, and then obtain an integer solution.

Problem Data

Crew Base

All crews are based at ORD. Every pairing must begin with a flight departing ORD and end with a flight arriving at ORD, all within one duty day.

Spoke Cities

Flight Schedule

MidwestAir operates 40 daily flight legs. All times are Central Time.

Crew Rules (Simplified)

A feasible pairing is a sequence of flight legs satisfying:

1. Base rule: The pairing begins with a flight departing ORD and ends with a flight arriving at ORD.

2. Connection time: Between consecutive flight legs, the minimum sit time is 30 minutes and the maximum sit time is 3 hours (at any city, including ORD).

3. Duty period: A duty period begins 45 minutes before the first departure and ends 15 minutes after the last arrival. Total duty time must not exceed 12 hours.

4. Flight time limit: Total flight time (block time) within the pairing cannot exceed 8 hours.

5. Maximum legs: A pairing contains at most 4 flight legs.

There are no multi-day pairings and no deadheading in this simplified version.

Cost Structure

The cost of a pairing is:

\[\text{Pairing Cost} = \max\left(\text{Flight Time Pay},\ \text{Daily Guarantee}\right) + \text{Per Diem}\]

A crew is paid the greater of flight time pay or the daily guarantee, plus per diem for the full duty period.

Your Assignment

Part 1: Problem Structure and Formulation

1. Master problem: Formulate the set covering master problem. Let \(\mathcal{P}\) be the set of all feasible pairings, \(x_p \in \{0,1\}\) for each pairing, \(a_{fp} = 1\) if pairing \(p\) covers flight \(f\), and \(c_p\) the cost of pairing \(p\). Write the formulation.

2. Problem scale: How many feasible pairings could exist? Explain why column generation is useful even though enumeration may be possible for this smaller instance.

3. Column generation framework: Describe:

   • What is the restricted master problem (RMP)?
   • What is the pricing subproblem? Given dual values \(\pi_f\) from the RMP, define the reduced cost of a pairing and explain how to find the pairing with the most negative reduced cost.
   • When does the algorithm terminate?

Part 2: Implementation

Implement the column generation algorithm in a Google Colab notebook. Use AMPL/Gurobi for the RMP and Python for pairing generation.

1. Enumerate all feasible pairings: With 40 flights, 6 cities, and max 4 legs per pairing, full enumeration is tractable. Write a Python function that generates all feasible pairings by exploring sequences of flights that satisfy the crew rules. Report how many feasible pairings exist.

2. Initial columns: Start the RMP with simple 2-leg out-and-back pairings (one outbound + one return for each city pair). Add artificial variables with cost $100,000 for any uncovered flights.

3. Column generation loop: Implement the loop:

   • Solve the RMP LP relaxation.
   • Extract dual values \(\pi_f\).
   • From the enumerated pairing pool, find the pairing with the most negative reduced cost.
   • Add it to the RMP.
   • Repeat until no negative reduced cost exists.
   • Log the objective value and column count at each iteration.

4. Convergence plot: Create a plot of the RMP objective value vs. iteration number.

Part 3: Integer Solution and Analysis

1. IP solution: After column generation converges, solve the final RMP as an integer program (binary \(x_p\)). Report the LP and IP objectives, the LP-IP gap, and the number of pairings used.

2. Solution details: For each pairing in the integer solution, list the flight sequence, flight time, duty time, and cost.

3. Crew utilization: What is the average number of legs per pairing? What is the average crew utilization (flight time / duty time)?

4. Comparison with full enumeration: Solve the set covering IP using the complete set of enumerated pairings (without column generation). Compare the objective and solve time to the column generation approach. Discuss the trade-off.

5. Executive summary: Write a 1-page summary for MidwestAir’s VP of Flight Operations covering the recommended crew schedule, total daily crew cost, and key efficiency metrics.

Hints and Guidance

• Start with 2-leg pairings: The simplest pairings are out-and-back (ORD → city → ORD). These cover most flights and give you a working initial RMP quickly.
• Enumeration approach: Use a depth-first search that builds pairing sequences leg by leg, pruning whenever a connection is infeasible (wrong city, sit time out of range, duty/flight time exceeded, too many legs). This keeps the enumeration manageable.
• Pairing cost: Compute flight time in hours by summing (arrival − departure) for each leg. Duty time = (last arrival + 15 min) − (first departure − 45 min). Pay = max(300 × flight_hours, 1100) + 2.00 × duty_hours.
• Adding columns in AMPL: You can rebuild the RMP data each iteration by writing new data, or use AMPL’s programmatic interface to add columns incrementally.

Deliverables

• A written formulation document (PDF or markdown) covering the master problem, subproblem, and column generation framework.
• A Google Colab notebook (.ipynb) with the enumeration code, column generation implementation, convergence plot, IP solution, analysis, and executive summary.