Markov Decision Processes and Discrete Optimization

这项拨款为研究两类重要的优化问题之间的联系提供了资金：随机动态规划，也被称为马尔可夫决策过程，和离散优化。本项目主要研究离散优化在随机动态规划中的应用，随机动态规划在离散优化中的应用，以及随机和离散优化在生产、服务、电信和监控系统中的应用。本课题的第一项任务是研究马尔可夫决策过程的分类问题。这些问题对于马尔可夫决策过程的高效算法的实现至关重要。第二个任务是通过马尔可夫决策过程研究离散优化问题的表示，并为某些离散优化问题开发新的解决方法。第三项任务是为几个生产、服务、电信和国土安全问题开发有效的算法。如果成功，这项研究将开发新的方法和算法来解决重要的优化问题。它将为马尔可夫决策过程开发分类算法，以识别其特定的结构属性。这些算法对于马尔科夫决策过程的有效优化非常重要，马尔科夫决策过程被广泛用于各种应用，如生产和服务系统的控制、人工智能中的强化学习和决策制定。该项目还将研究重要的离散优化问题的新方法，包括哈密顿循环、旅行推销员和广义风车问题。这些方法是基于离散优化问题的马尔可夫决策过程表示，并研究这些表示的性质。该项目将通过开发高效的调度、准入和资源分配算法，为某些生产、服务和电信应用开发新的解决方案技术。此计划将有助发展科学及工程方面的人力资源、推动科技进步，以及促进产业界与学术界的互利互动。

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.