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)解算器的性能在过去几十年中有了极大的提高，但供应链和医疗物流(SCL)中的许多离散决策问题仍然具有挑战性。这项研究计划的重点将是开发图形优化模型(GOM)，以便为Schl中的离散决策问题产生更快的解。 术语“图形模型”传统上是指表达随机变量之间的条件依赖结构的概率图形模型。然而，在离散优化的背景下，我们使用术语GOM来表示一大类基于图的模型，这些模型描述了具有状态和动作变量的系统以及一组连接方程。在文献中，这种GOM被用来构建动态规划(DP)、具有网络流组件的MIP公式、依赖于列或行生成的分解方法以及CP中的全局约束。 与单纯依赖连续(线性或非线性)松弛的方法相比，GOM的主要优势是它们在表示离散决策方面提高了精度。这些模型需要相当大的内存来构建和操作，随着内存可用性和成本的提高，它们正变得越来越有用。在这个提案中，我们将重点讨论从超图(HG)和决策图(DDS)派生的GOM，它们已经成功地用于优化环境中。 我的研究计划的四个主要目标是使用GOM：1)建立新一代离散求解器；2)更好地模拟SCL问题中的不确定性；3)支持用于组合优化的深度强化学习(DRL)；以及4)实时解决工业SCL问题。 我们的目标是既有方法上的影响，也有实践上的影响。这项研究将a)为我们的加拿大初创合作伙伴提供新的工具，使他们能够在全球范围内竞争并取得成功，以及b)帮助我们的加拿大公共服务和医疗保健合作伙伴更有效地照顾人口。该计划将培训的12名高素质人员(HQP)预计将作为科学家或领域专家加入学术界或行业。