Optimization Algorithms for New Computer Architectures with Applications to Routing and Scheduling
Abstract
Many Air Force applications can be modeled as some extension of a pure network problem. These extensions may require additional side constraints, arcs that involve attrition or flow of multiple commodities on a single arc. In all cases, the network models require integer programming model. Since some of these applications demand computer hardware several orders of magnitude faster than the fastest machines available, we have investigated the use of parallelism to increase the computational speed of these algorithms. Very powerful hardware (in terms of millions of floating point operations per second) can be built using many low cost standard chips, all designed to operate in parallel. Our research program objective is to develop and empirically test new serial and parallel algorithms and software for network based models. The problems studied during the past eighteen months include the generalized network problem, the transportation problem, sparse and dense assignment problems, the one-to-one shortest path problem problem, and the singly constrained assignment problem. Algorithms for all of these models have been developed and empirically tested on a variety of sequential and parallel computers.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 20, 1992
- Accession Number
- ADA251959
Entities
People
- Jeffrey L. Kennington
Organizations
- Southern Methodist University