Next: Traveling Salesperson Problem Up: Set Covering Previous: Set Covering

### Set Packing and Partitioning

Other problems involving relationships between a set and some of its subsets are related to set covering. The set packing problem arises when each set element must appear in at most one subset. In this case, the constraints are of the less-than-or-equal form. The set partitioning problem arises when each set element must appear in exactly one subset, and the constraints in this problem are equality constraints.

One interesting (and profitable!) area where set partitioning is used is in airline crew scheduling. Next to fuel costs, personnel costs are the largest cost an airline faces; captain salaries of \$150,000 per year are not unusual. The effective use of personnel can have a tremendous impact on the bottom line. There are, however, a tremendous number of restrictions on how airline personnel are used. Between FAA regulations and union contracts, determining a feasible crew schedule is a very difficult problem. About ten years ago, American Airline was interested in applying OR techniques to crew scheduling. In their formulation, a variable is created for each feasible schedule for a single crew. For instance, a schedule where the crew leaves Pittsburgh at 7:15AM on Tuesday, arrives in NY at 8:30, leaves NY at 9:00, arrives Atlanta at 11:00, leaves Atlanta at 12:00 and arrives Pittsburgh at 2:30 would correspond to a single variable, , say. The cost of setting that variable to 1 (meaning to have a crew fly that schedule) would be based on the union contract and other regulations.

As you can imagine, there are a tremendous number of variables. The constraints, however are very simple. For each flight (called a leg), it is necessary to choose a schedule that includes that flight. This leads to a constraint of the form

if schedules 1, 4, 55, 5534 and so on all contain the 7:15 Tuesday flight from Pittsburgh to NY (for example). While the resulting is very large, the savings that result from finding good solutions are so large that a tremendous amount of work has gone into finding techniques for solving these problems. In fact, the group within American has spun off into a consulting operation (now part of Sabr Technologies), and is one of the most profitable areas for American Airlines.

Next: Traveling Salesperson Problem Up: Set Covering Previous: Set Covering

Michael A. Trick
Sun Jun 14 12:49:07 EDT 1998