Analysis and Algorithms for Countably Infinite Linear Programming Models of Markov Decision Processes

该奖项的目的是为可数无限线性优化问题（CILP）的一大子类提供理论分析和解决方法，即，变量和约束的数量是可数无穷的线性规划问题。CILP出现在各种应用中，包括无限时域非平稳马尔可夫决策过程（MDP）和具有可数无限状态空间的平稳MDP，有约束和无约束。这项工作将建立一个强大的理论，算法和计算框架，这尚未开发领域的数学优化，建立条件下，重要的理论和算法的结果，从发达领域的有限LP可以扩展到重要类的CILP。这包括开发和严格的理论分析的单纯形类算法的非平稳MDP和改进和广泛的测试这些算法的计算性能。此外，该研究将现有的和新的理论和算法的结果扩展到CILP表示的其他重要类型的MDP，包括固定的MDP与可数无限的状态空间，和非固定的无限地平线MDP与边约束。这项工作的结果将加深目前的理解CILP的基本结构特性，并导致发展新的算法方法来找到他们的解决方案。此外，这项研究将直接有助于更好的分析和解决工具，为许多类型的问题，长期规划下的不确定性，包括应用在经济，金融，制造和服务运营管理。根据该奖项开发的理论结果和算法解决方法将使决策者能够更好地理解此类问题中最佳决策的结构和行为，特别是更好地理解今天做出更好决策的能力与所需的未来预测量之间的相互作用。根据该奖项开发的软件将在线分发和记录，研究生将从这项工作产生的研究参与和课程开发中受益。

The objective of this award is to provide theoretical analysis and solution methods for a large sub-class of countably infinite linear optimization problems (CILPs), i.e., linear programming problems in which the number of variables and constraints is countably infinite. CILPs arise in a variety of applications, including infinite-horizon non-stationary Markov Decision Processes (MDPs) and stationary MDPs with countably infinite state spaces, both with and without constraints. This work will build a strong theoretical, algorithmic and computational framework for this as yet underdeveloped field of mathematical optimization, establishing conditions under which important theoretical and algorithmic results from the well developed field of finite LPs can be extended to important classes of CILPs. This includes development and rigorous theoretical analysis of simplex-like algorithms for non-stationary MDPs and improvements and extensive tests of the computational performance of these algorithms. Moreover, the research will extend existing and new theoretical and algorithmic results to CILP representations of other important types of MDPs, including stationary MDPs with countably infinite state spaces, and non-stationary infinite-horizon MDPs with side constraints.The results of this work will deepen the current understanding of the fundamental structural properties of CILPs, and lead to development of new algorithmic approaches to find their solutions. Moreover, this research will directly contribute to better analysis and solution tools for many types of problems of long-term planning under uncertainty, including applications in economics, finance, and manufacturing and service operations management. Theoretical results and algorithmic solution methods developed under this award will enable decision makers to better understand the structure and behavior of optimal decisions in such problems, and in particular to better understand the interplay between the ability to make better decisions today and the amount of future forecasting required. Software developed under this award will be distributed and documented online, and graduate students will benefit from research participation and curriculum development resulting from this work.