Optimal Resource Allocation under Uncertainty

本研究的目标是开发系统的算法和技术，以快速搜索资源分配问题的最优或接近最优解决方案。研究方法，即嵌套分区（NP）方法，将被扩展和测试，以解决行业合作伙伴遇到的资源分配问题。许多资源分配问题，如设施规划、工作调度、污染控制和投资组合管理，都可以建模为离散随机优化问题。由于这些系统固有的复杂性，分配和调度策略的设计可能是一项艰巨的任务。一个关键问题是备选方案的组合爆炸，通常会导致np完全优化问题。除了“玩具问题”之外，即使是为解决现实问题而开发的最优雅、最有效的方法，也会面临计算复杂性的障碍。在动态系统的情况下，不确定因素的增加使情况更加恶化，使这些问题进一步复杂化。预计这一发展将在复杂系统设计、控制、评估和优化领域产生实际和理论影响。这项研究将允许设计者或管理者检查一个大的解决方案空间，以产生具有可预测行为的系统，这将被证明是具有成本效益的，并提高系统的质量。该研究的发展也将为解决许多其他随机优化问题提供一个框架。

The goal of this research is to develop systematic algorithms and techniques for rapidly searching an optimal or near optimal solution of a resource allocation problem. The research method, the Nested Partitions (NP) method, will be extended and tested to solve resource allocation problems encountered by industry partners. Many resource allocation problems such as facility planning, job scheduling, pollution control, and portfolio management can be modeled as discrete stochastic optimization problems. Owing to the complexity inherent in these systems, the design of allocation and scheduling policies can be a formidable task. One key issue is the combinatorial explosion of alternatives normally leading to NP-complete optimization problems. Beyond "toy problems", computational complexity is an obstacle faced by even the most elegant and effective approaches developed for solving realistic problems. In the case of dynamic systems, the situation is exacerbated by the added elements of uncertainty, which further complicate such problems. It is expected that this development will exert both a practical and theoretical impact in the area of complex system design, control, evaluation and optimization. This research will allow the designer or manager to examine a large solution space to produce systems with predictable behavior which would prove to be cost effective and improve the quality of the systems. The research development will also provide a framework for solving many other stochastic optimization problems.