|
The solution strategy called for generating several million good pairings as candidates, formulating the world as a Linear Programming (LP) model (selection or covering type model), using high performance machines, an extremely powerful LP solver, and lots of heuristics.
The pairings were generated by duty generation (dhds selection), network generation (arcs selection), and pairing generation (deleting of duplicates).
The LP solution used the SPRINT idea, an algorithm, developed at IBM Watson in Yorkstown, NY, to solve huge LP problems of a certain type with a reasonable amount of constraint (several thousands) and a large number of variables (several millions).
Solution stages included optimal continuous LP, heuristic fixing, and standard B&B.
| 
