Accelerating ATM Optimization Algorithms Using High Performance Computing Hardware Project

Description

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.

General Information

• This data is described at

  http://catalog.data.gov/dataset/accelerating-atm-optimization-algorithms-using-high-performance-computing-hardware-project-5bdd5 Do you think this data is incorrect? Let us know

• This data is published by

  National Aeronautics and Space Administration Do you think this data is incorrect? Let us know

Legal Information

• The rights statement is at

  http://catalog.data.gov/dataset/accelerating-atm-optimization-algorithms-using-high-performance-computing-hardware-project-5bdd5 Do you think this data is incorrect? Let us know

• Outside the US, this data is available under

  Creative Commons CCZero Do you think this data is incorrect? Let us know

• There are

  yes, and the rights are all held by the same person or organisation Do you think this data is incorrect? Let us know

• The content is available under

  Creative Commons CCZero Do you think this data is incorrect? Let us know

• The rights statement includes data about

  its data licence Do you think this data is incorrect? Let us know

• This data contains

  no data about individuals Do you think this data is incorrect? Let us know

Practical Information

• The data appears in this collection

  http://catalog.data.gov/organization/nasa-gov Do you think this data is incorrect? Let us know

• The accuracy or relevance of this data will

  go out of date but it is timestamped Do you think this data is incorrect? Let us know

• The data is

  backed up offsite Do you think this data is incorrect? Let us know

Technical Information

• This data is published at

  http://techport.nasa.gov/xml-api/9311 Do you think this data is incorrect? Let us know

• This data is

  machine-readable Do you think this data is incorrect? Let us know

• The format of this data is

  a standard open format Do you think this data is incorrect? Let us know

Social Information

• The documentation includes machine-readable data for

  title Do you think this data is incorrect? Let us know

• The documentation includes machine-readable data for

  description Do you think this data is incorrect? Let us know

• The documentation includes machine-readable data for

  identifier Do you think this data is incorrect? Let us know

• The documentation includes machine-readable data for

  landing page Do you think this data is incorrect? Let us know

• The documentation includes machine-readable data for

  publisher Do you think this data is incorrect? Let us know

• The documentation includes machine-readable data for

  keyword(s) or tag(s) Do you think this data is incorrect? Let us know

• The documentation includes machine-readable data for

  distribution(s) Do you think this data is incorrect? Let us know

• The documentation includes machine-readable data for

  release date Do you think this data is incorrect? Let us know

• The documentation includes machine-readable data for

  modification date Do you think this data is incorrect? Let us know

• The documentation includes machine-readable data for

  temporal coverage Do you think this data is incorrect? Let us know

• The documentation includes machine-readable data for

  language Do you think this data is incorrect? Let us know

• The documentation about each distribution includes machine-readable data for

  release date Do you think this data is incorrect? Let us know

• The documentation about each distribution includes machine-readable data for

  a URL to access the data Do you think this data is incorrect? Let us know

• The documentation about each distribution includes machine-readable data for

  a URL to download the dataset Do you think this data is incorrect? Let us know

• The documentation about each distribution includes machine-readable data for

  type of download media Do you think this data is incorrect? Let us know

• Find out how to contact someone about this data at

  http://catalog.data.gov/dataset/accelerating-atm-optimization-algorithms-using-high-performance-computing-hardware-project-5bdd5 Do you think this data is incorrect? Let us know

• Find out how to suggest improvements to publication at

  http://www.data.gov/issue/?media_url=http://catalog.data.gov/dataset/accelerating-atm-optimization-algorithms-using-high-performance-computing-hardware-project-5bdd5 Do you think this data is incorrect? Let us know