NASA is developing algorithms and methodologies for efficient air-traffic management. Several researchers have adopted an optimization framework for solving problems such as flight scheduling, route assignment, flight rerouting, nationwide traffic flow management (TFM) and dynamic airspace configuration. Computational complexity of these problems have led investigators to conclude that in many instances, real time solutions are computationally infeasible, forcing the use of relaxed versions of the problem to manage computational complexity. The primary objective of the proposed research is to accelerate optimization algorithms that play central roles in NASA's ATM research, by parallel implementation on emerging high performance computing (HPC) hardware. The Phase I R&D effort implemented a Simplex-based Dantzig-Wolfe (DW) decomposition solver that exploits both coarse-grain and fine-grain parallelism in the sub-problem and master iterations of the DW decomposition. The implementation also exploits the sparsity in the problems, to manage both memory requirements and run-times for large-scale optimization problems. This parallel implementation was used to solve a Traffic Flow Management (TFM) problem with 17,000 aircraft (linear program with 7 million constraints), in 15 seconds. The implementation is 30¿ faster than the exact same code running on the CPU. It is also 16¿ faster than the NASA's current solution that implements parallel DW decomposition using the GNU Linear Programming Kit (GLPK) on an 8-core computer with hyper-threading. Based on the promising Phase I results, the Phase II R&D effort will explore Mixed Integer Linear Programming (MILP) methods to solve optimization problems arising in the terminal area and on the airport surface, in addition to DW decomposition for the nationwide TFM problem. Phase II work will develop operational prototypes of the algorithm implementations on HPC hardware, and deliver them to NASA for further evaluation.
More »Proposed R&D effort will enable rapid solution to large scale optimization problems formulated by NASA researchers in the air traffic domain such as flight scheduling, route assignment, flight rerouting, national traffic flow management and dynamic airspace reconfiguration. The optimization software suite will enable real time execution of many optimizations problems that were deemed infeasible due to computational complexity. The software suite developed under the proposed research will enable solutions to such problems without resorting to approximations.
High-complexity large-scale optimization problems arise frequently in the industry in several areas, such as: 1) Layout planning: designing the layout of equipment in a factory or components on a computer chip to reduce manufacturing time and minimize cost, 2) Network optimization: setup of telecommunications networks to maintain maximum throughput and quality of service during outages, 3) Resource allocation problems, optimal search and routing, 4) Supply chain management: managing the flow of raw materials and products based on uncertain demand for the finished products, 5) Transportation: managing freight transportation and delivery systems, 6) Scheduling applications: personnel staffing, manufacturing steps, project tasks, network data traffic, sports events and their coverage. The accelerated optimization software suite developed under this R&D effort will enable faster runtimes making it practical to deploy them more widely in operations.
Organizations Performing Work | Role | Type | Location |
---|---|---|---|
Optimal Synthesis, Inc. | Lead Organization |
Industry
Minority-Owned Business,
Small Disadvantaged Business (SDB)
|
Los Altos, California |
Ames Research Center (ARC) | Supporting Organization | NASA Center | Moffett Field, California |