Accelerating ATM Optimization Algorithms Using High Performance Computing Hardware

Award Information
Agency:
National Aeronautics and Space Administration
Branch
n/a
Amount:
$900,000.00
Award Year:
2012
Program:
SBIR
Phase:
Phase II
Contract:
NNX12CA05C
Award Id:
n/a
Agency Tracking Number:
105968
Solicitation Year:
2010
Solicitation Topic Code:
A3.01
Solicitation Number:
n/a
Small Business Information
CA, Los Altos, CA, 94022-2777
Hubzone Owned:
N
Minority Owned:
N
Woman Owned:
N
Duns:
829385509
Principal Investigator:
Prasenjit Sengupta
Principal Investigator
(650) 559-8585
sengupta@optisyn.com
Business Contact:
P. K. Menon
Business Official
(650) 559-8585
menon@optisyn.com
Research Institute:
Stub




Abstract
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.

* information listed above is at the time of submission.

Agency Micro-sites


SBA logo

Department of Agriculture logo

Department of Commerce logo

Department of Defense logo

Department of Education logo

Department of Energy logo

Department of Health and Human Services logo

Department of Homeland Security logo

Department of Transportation logo

Enviromental Protection Agency logo

National Aeronautics and Space Administration logo

National Science Foundation logo
US Flag An Official Website of the United States Government