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

AF：小：优化问题近似算法设计的进展

• 批准号: 1017688
• 负责人: David Shmoys
• 金额: $ 49.96万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1017688&HistoricalAwards=false
• 关键词: AF; Small; AAdvances; Design; Approximation

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.

对于大多数在工业中使用优化算法的应用，特别是物流、供应链管理、路由和网络设计等问题，计算问题是难以解决的——输入数据的大小有严格的限制，这些限制可以快速可靠地求解到最优。我们将专注于新算法技术的发展，在算法设计中为这些关键问题提供良好的解决方案。这些算法的理论基础是它们具有性能保证，确保计算出的解接近最优；例如，该项目旨在设计有效的算法，以找到成本不超过指定百分比的解决方案，而不是最小可能的解决方案。该项目还考虑了随机优化问题，其中输入由输入的概率分布组成，从而产生比输入是确定的更困难的问题。我们将专注于问题的表述和方法，使我们能够利用历史数据档案对必要的概率分布进行建模。该项目旨在为许多理论模型提供强大保证的算法，包括在许多工业环境中出现的容量设施定位问题，从配送网络中的仓库定位到高带宽网络中集线器位置的选择；广义分配问题在异构环境中具有广泛的工作负载平衡应用；瓶颈不对称旅行推销员问题（TSP），该问题出现在化学加工厂的调度中（技术上称为无等待流程车间调度环境），以及更经常研究的最小和变体；提出了几种随机优化模型，其中包括医疗运输机自适应航路优化模型。找到提高物流规划效率的好方法对整个美国经济来说都是一个重要的问题，这也是这个项目的长期目标。我们的观点是，对简化模型的研究将产生可应用于具有工业规模数据和复杂性的现实设置的算法范例。证明所发现的解决方案质量的强大定理所需的洞察力转化为算法原则，这反过来又导致算法能够很好地解决行业需要解决的问题。通过培训该领域的研究生，该项目还将为确保美国劳动力拥有足够的专业知识以应对下个世纪物流支持领域的技术挑战做出重要贡献。