Nearly Optimal Solutions for Stochastic Optimization Problems

这项拨款为开发优化工具和数据结构提供资金，用于广泛的确定性和随机优化问题。这些工具的目的是帮助逼近算法的开发和自动分析，特别是随机优化问题的逼近算法。研究的重点是随机动态规划的全多项式时间逼近方案。这些算法保证得到的解在任何指定的小误差范围内，并且运行时间是问题大小的多项式和误差的反比。在近似算法类中，FPTASs提供了保证精度与计算时间的最佳权衡。为了开发高效的FPTASs，该研究将开发用于表示和操作近似函数的对象集合，以及用于这些对象的算法库，这些对象可以很容易地被其他研究人员使用。如果成功，该项目将导致改进算法的随机优化问题出现在几个不同的研究领域，包括：供应链管理，经济学，调度和数学金融。本研究将为这些领域的基本问题，如单项目库存控制、资本预算、动态产能扩张、时间成本权衡机器调度、批量处置和共同基金现金管理，开发有效的算法。随后，这些基本问题的有效方法可以作为这些领域中更复杂和现实问题的子程序。提议的工作还将导致新的数据结构和数据对象，这将促进在这些和其他领域出现的近似算法的开发和分析。

This grant provides funding for the development of optimization tools and data structures for a wide class of deterministic and stochastic optimization problems. The purpose of the tools is to aid in the development and automated analysis of approximation algorithms, especially approximation algorithms for stochastic optimization problems. The research will focus on Fully Polynomial Time Approximation Schemes (FPTASs) for stochastic dynamic programs. These algorithms guarantee obtaining a solution that is within any specified small error, and where the running time is polynomial in the size of the problem and the inverse of the error. Within the class of approximation algorithms, FPTASs offer the best tradeoffs of guaranteed accuracy versus computational time. In order to develop efficient FPTASs, the research will develop a collection of objects for representing and manipulating approximated functions, as well as a library of algorithms for these objects that can readily be used by other researchers.If successful, the project will lead to improved algorithms for stochastic optimization problems that arise in several different fields of study including: supply chain management, economics, scheduling and mathematical finance. The research will develop efficient algorithms for fundamental problems in these fields such as single-item inventory control, capital budgeting, dynamic capacity expansion, time-cost tradeoff machine scheduling, batch disposal, and mutual fund cash management. Subsequently, the efficient approaches for the fundamental problems can be used as subroutines in more complex and realistic problems in these fields. The proposed work will also lead to new data structures and data objects that will facilitate the development and analysis of approximation algorithms that arise in these and other fields.