Approaches to the Variable Crewing problem in Pairing

摘要

1. TRIP, ALLPS (1980's) 1.1 Iterative: enumeration for a limited subproblem 2. Subselection tricks (Housos and Elmroth, 1997) 3. Sprint (partial pricing) 1992 4. Column generation (Minoux, 1984) 4.1 ALTITUDE-Ad Opt 5. Ryan and Falkner (1988) - constraint branching 6. Anbil, Forrest, and Pulleyblank (1998) 6.1 Heuristic depth first search guided by duals 6.2 Volume algorithm for master (extension of subgradient).