标题： 带有部分信息的弱耦合随机动态规划的整数规划 显示英文标题

标题： Integer programming for weakly coupled stochastic dynamic programs with partial information

摘要： 本文介绍了在决策者必须控制由多个组件组成的系统并且只能获得每个组件状态的部分信息的问题的算法。 此类问题具有挑战性，因为存在部分观测问题，并且当组件数量增加时会出现维度灾难问题。 部分可观测马尔可夫决策过程（POMDPs）被引入以处理第一个挑战，而弱耦合随机动态规划则处理第二个挑战。 结合文献中的这两个分支，我们引入了弱耦合POMDP的概念。 目标是找到一个策略，在有限时间范围内最大化总期望奖励。 我们的算法依赖于两个要素。 第一个要素可以独立使用，是一个针对通用POMDP的混合整数线性公式，用于计算最优的无记忆策略。 该公式通过基于随机变量之间依赖关系的概率解释的有效切割进行强化，其线性松弛为最优历史依赖策略的价值提供了实际紧致的上界。 第二个要素是一系列数学规划公式和算法，这些公式和算法为弱耦合POMDP提供可行的策略和上界。 拉格朗日松弛、流近似和几乎必然约束松弛有助于克服维度灾难。 我们在文献中的基准实例上测试了我们的通用POMDP公式，并在维护问题上测试了我们的弱耦合POMDP算法。 数值实验表明了我们方法的效率。 显示英文摘要

摘要： This paper introduces algorithms for problems where a decision maker has to control a system composed of several components and has access to only partial information on the state of each component. Such problems are difficult because of the partial observations, and because of the curse of dimensionality that appears when the number of components increases. Partially observable Markov decision processes (POMDPs) have been introduced to deal with the first challenge, while weakly coupled stochastic dynamic programs address the second. Drawing from these two branches of the literature, we introduce the notion of weakly coupled POMDPs. The objective is to find a policy maximizing the total expected reward over a finite horizon. Our algorithms rely on two ingredients. The first, which can be used independently, is a mixed integer linear formulation for generic POMDPs that computes an optimal memoryless policy. The formulation is strengthened with valid cuts based on a probabilistic interpretation of the dependence between random variables, and its linear relaxation provide a practically tight upper bound on the value of an optimal history-dependent policies. The second is a collection of mathematical programming formulations and algorithms which provide tractable policies and upper bounds for weakly coupled POMDPs. Lagrangian relaxations, fluid approximations, and almost sure constraints relaxations enable to break the curse of dimensionality. We test our generic POMDPs formulations on benchmark instance forms the literature, and our weakly coupled POMDP algorithms on a maintenance problem. Numerical experiments show the efficiency of our approach.