AF: Small: AAdvances in the Design of Approximation Algorithms for Optimization Problems

点击翻译按钮获取中文摘要

For most applications in which optimization algorithms are used in industry, and in particular problems from logistics, supply-chain management, routing, and network design, the computational problems are intractable -- there are severe restrictions on the size of input data that can be quickly and reliably solved to optimality. We will focus on the development of new algorithmic techniques in the design of algorithms to produce good solutions for these critical problems. The theoretical foundation of these algorithms is that they possess a performance guarantee that assures that the solutions computed are nearly optimal; for example, the project aims to devise efficient algorithms to find solutions for which the cost is no more than a specified percentage more than the minimum possible. The project also considers stochastic optimization problems, where the input consists of a probability distribution over inputs, thereby giving rise to even more difficult problems than if the input is known with certainty. We will focus on problem formulations and approaches that allow us to model the requisite probability distributions using historical data archives.This project aims to provide algorithms with strong guarantees for a number of theoretical models including the capacitated facility location problem, which arises in many industrial contexts from the positioning of warehouses in a distribution network to the choice of hub placements in high-bandwidth networks; the generalized assignment problem, which has a range of workload-balancing applications in heterogeneous environments; the bottleneck asymmetric traveling salesman problem (TSP), which arises in scheduling of chemical processing plants (known technically as a no-wait flowshop scheduling environment), as well as the more often studied minimum-sum variant; and several stochastic optimization models including one arising from the adaptive routing of medical transport planes.Finding good approaches to gain new efficiencies in logistical planning is an issue that is important for the overall US economy, and this is a long-term goal of this project. Our viewpoint is that the study of simplified models will yield algorithmic paradigms that can be applied to realistic settings with industry-scale data and complexities. The insight needed to prove strong theorems about the quality of the solutions found translates into algorithmic principles, which in turn leads to algorithms that work well on the problems that industry needs to solve. By training graduate students in this area, this project will also contribute to the important effort to ensure that the US workforce has sufficient expertise to meet the technological challenges of the coming century in the area of logistics support.