This grant provides funding for the investigation of the links between two important classes of optimization problems: stochastic dynamic programming, also known under the name of Markov Decision Processes, and discrete optimization. In particular, this project studies applications of discrete optimization to stochastic dynamic programming, applications of stochastic dynamic programming to discrete optimization, and applications of stochastic and discrete optimization to production, service, telecommunication, and surveillance systems. The first task of this project studies classification problems for Markov Decision Processes. These problems are important for the implementation of efficient algorithms for Markov Decision Processes. The second task investigates representations of discrete optimization problems via Markov Decision Processes and develops new solution methods for certain discrete optimization problems. The third task develops efficient algorithms for several production, service, telecommunication, and homeland security problems.
If successful, this research will develop new methodologies and algorithms to solve important optimization problems. It will develop classification algorithms for Markov Decision Processes that identify their specific structural properties. Such algorithms are important for efficient optimization of Markov Decision Processes, which are broadly used for various applications such as control of production and service systems, reinforcement learning in artificial intelligence, and decision making. This project will also study new approaches to important discrete optimization problems including the Hamiltonian Cycle, Traveling Salesman, and Generalized Pinwheel Problems. These approaches are based on the representations of discrete optimization problems via Markov Decision Processes and studying the properties of these representations. This project will develop new solution techniques for certain production, service, and telecommunication applications by developing efficient scheduling, admission, and resource allocation algorithms. This project will contribute to the development of human resources in science and engineering, to technological progress, and to mutually beneficial interactions between industry and academia.
