Exploiting Graphical Optimization Models to Solve Discrete Decision Problems in Healthcare and Supply Chain Logistics

利用图形优化模型解决医疗保健和供应链物流中的离散决策问题

• 批准号: RGPIN-2019-05941
• 负责人: Rousseau, LouisMartin
• 金额: $ 4.52万
• 依托单位: École Polytechnique de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=759430
• 关键词: Exploiting; Graphical; Optimization; Models; Solve

Despite a tremendous increase in the performance of mixed integer programming (MIP) and constraint programming (CP) solvers during the past few decades, many discrete decision problems in supply chain and healthcare logistics (SCHL) remain challenging. The focus of this research program will be on the development of graphical optimization models (GOMs) to yield faster solutions for discrete decision problems in SCHL. The term "graphical model" traditionally refers to a probabilistic graphical model that expresses the conditional dependence structure between random variables. However, in the context of discrete optimization, we use the term GOM to represent a broad class of graph-based models that describe a system with states and action variables and a set of linking equations. In the literature, such GOMs are used to build dynamic programs (DP), MIP formulations with network flow components, decomposition approaches that rely on column or row generation, and global constraints in CP. The main advantage of GOMs is their increased precision in representing discrete decisions compared to methods that rely solely on continuous (linear or nonlinear) relaxations. These models, which require considerable memory to build and manipulate, are becoming increasingly useful as the availability and cost of memory improve. In this proposal, we will focus on GOMs derived from hypergraphs (HG) and decision diagrams (DDs), which have been successfully used in the context of optimization. The four main objectives of my research program are to use GOMs: 1) to build a new generation of discrete solvers; 2) to better model uncertainty in SCHL problems; 3) to support deep reinforcement learning (DRL) for combinatorial optimization; and 4) to solve industrial SCHL problems in real time. We aim to have both a methodological and a practical impact. The research will a) provide our Canadian startup partners with new tools that will allow them to compete and succeed on a global scale, and b) help our Canadian public service and healthcare partners to be more efficient in caring for the population. The 12 highly qualified personnel (HQP) that will be trained by this program are expected to join academia or industry as scientists or domain experts.

尽管在过去的几十年中，混合整数规划（MIP）和约束规划（CP）求解器的性能有了很大的提高，但供应链和医疗物流（SCHL）中的许多离散决策问题仍然具有挑战性。本研究计划的重点将是图形优化模型（GOM）的发展，以产生更快的解决方案，在SCHL离散决策问题。 “图模型”一词传统上是指概率图模型，它表达了随机变量之间的条件依赖结构。然而，在离散优化的上下文中，我们使用术语GOM来表示一类广泛的基于图的模型，这些模型描述了具有状态和动作变量以及一组链接方程的系统。在文献中，这样的GOM被用来建立动态程序（DP），MIP配方与网络流组件，分解方法，依赖于列或行生成，和CP中的全局约束。 GOM的主要优点是，与仅依赖于连续（线性或非线性）松弛的方法相比，它们在表示离散决策时的精度有所提高。这些模型需要大量的内存来构建和操作，随着内存可用性和成本的提高，它们变得越来越有用。在本提案中，我们将重点关注来自超图（HG）和决策图（DD）的GOM，它们已成功地用于优化。 我的研究计划的四个主要目标是使用GOM：1）构建新一代离散求解器; 2）更好地建模SCHL问题中的不确定性; 3）支持深度强化学习（DRL）进行组合优化; 4）真实的时间解决工业SCHL问题。 我们的目标是在方法上和实际上产生影响。这项研究将a）为我们的加拿大创业合作伙伴提供新的工具，使他们能够在全球范围内竞争并取得成功，B）帮助我们的加拿大公共服务和医疗保健合作伙伴更有效地照顾人口。该计划将培训12名高素质人员（HQP），预计将作为科学家或领域专家加入学术界或工业界。