Massively Parallel Dantzig-Wolfe Decomposition Applied to Traffic Flow Scheduling

Optimal scheduling of traffic over the National Airspace System is computationally difficult. To speed computation, Dantzig-Wolfe decomposition is applied to a linear integer programming approach for assigning delays to flights. The subproblems for this decomposition are solved in parallel via independent computation threads. Experimental evidence suggests that as the number of subproblems/threads increases (and their sizes decrease) for a given problem, the solution quality, convergence, and runtime improve. A demonstration of this is provided by using the finest possible decomposition: one flight per subproblem. This massively parallel approach is compared with one with few threads and with non-decomposed approaches in terms of solution quality and runtime. Since this method generally provides a relaxed solution to the original integer optimization problem, two heuristics are developed to generate an integral solution. Dantzig-Wolfe followed by these heuristics can provide a near-optimal (sometimes optimal) solution to the original problem hundreds of times faster than the standard (non-decomposed) approaches. In addition, when massive decomposition is employed, the solution is shown to be more likely integral, which obviates the need for an integerization step. These results indicate that nationwide, real-time, high-fidelity, optimal traffic flow scheduling is achievable for (at least) 3-h planning horizons.