Solving large scale crew scheduling problems

Sabre Decision Technologies' Crew_Solve optimization algorithm for solving American Airlines' crew pairing problem enabled the airline to minimize costs by improving crew utilization and reducing pay and credit. The procedure, which recast the problem as a set partitioning zero-one integer program, employs linear program relaxations to trim the search tree and a graph-based branching heuristic to a 15,000-column set partitioning subproblem.