Optimization Algorithms for New Computer Architectures with Applications toRouting and Scheduling

摘要

Many Air Force applications can be modeled as some extension of a pure networkproblem. 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.