Solving large airline crew scheduling problems: Random pairing generation and strong branching

The airline crew scheduling problem is the problem of assigning crew itiner aries to flights. We develop a new approach for solving the problem that is based on enumerating hundreds of millions random pairings. The linear prog ramming relaxation is solved first and then millions of columns with best r educed cost are selected for the integer program. The number of columns is further reduced by a linear programming based heuristic. Finally an integer solution is obtained with a commercial integer programming solver. The bra nching rule of the solver is enhanced with a combination of strong branchin g and a specialized branching rule. The algorithm produces solutions that a re significantly better than ones found by current practice.