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
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=715854
• 关键词: 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 公式、依赖于列或行生成的分解方法以及全局约束。 C.P. 与仅依赖连续（线性或非线性）松弛的方法相比，GOM 的主要优点是在表示离散决策方面具有更高的精度。这些模型需要大量内存来构建和操作，随着可用内存和成本的提高，它们变得越来越有用。在本提案中，我们将重点关注从超图 (HG) 和决策图 (DD) 派生的 GOM，它们已成功地应用于优化领域。 我的研究计划的四个主要目标是使用 GOM：1）构建新一代离散求解器；2）更好地对 SCHL 问题中的不确定性进行建模；3）支持深度强化学习（DRL）以进行组合优化；4） ）实时解决工业 SCHL 问题。 我们的目标是产生方法论和实际影响，该研究将a）为我们的加拿大初创合作伙伴提供新工具，使他们能够在全球范围内竞争并取得成功，b）帮助我们的加拿大公共服务和医疗保健合作伙伴通过该计划培训的 12 名高素质人员 (HQP) 预计将作为科学家或领域专家加入学术界或工业界。