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.
