Air Anton is a small commuter airline running 6 flights per day from New York City to surrounding resort areas. Flight crews are all based in New York, staffing flights to various locations and then returning on the next flight home. Taking into account complex work rules and pay incentives, Air Anton schedulers have constructed the 8 possible work patterns detailed in the following table. Each row of the table marks the flights that could be covered in a particular pattern and the daily cost per crew (in thousands of dollars).

Work Pattern Flight 1 2 3 4 5 6 Cost 1 — * — * — — 1.40 2 * — — — — * 0.96 3 — * — * * — 1.52 4 — * — — * * 1.60 5 * — * — — * 1.32 6 — — * — * — 1.12 7 — — — * — * 0.84 8 * — * * — — 1.54 The company wants to choose a minimum total cost collection of work patterns that covers all flights exactly once.

(a) Formulate this problem as a set partitioning ILP.

(b) Use class optimization software to solve your ILP.