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公式，依赖列或行生成的分解方法以及CP中的全局约束。 与仅依赖连续（线性或非线性）放松的方法相比，GOM的主要优点是它们在表示离散决策方面的精度提高。这些模型需要考虑内存才能构建和操纵，随着记忆改善的可用性和成本，越来越有用。在此提案中，我们将重点关注来自超图（HG）和决策图（DDS）的GOM，这些GOM已在优化的背景下成功使用。 我的研究计划的四个主要目标是使用GOM：1）建立新一代的离散求解器； 2）更好地模拟SCHL问题中的不确定性； 3）支持深化学习（DRL）进行组合优化； 4）实时解决工业SCHL问题。 我们的目标是产生方法论和实际影响。研究将a）为我们的加拿大初创伙伴提供新工具，使他们能够在全球范围内竞争并取得成功，b）帮助我们的加拿大公共服务和医疗合作伙伴更有效地照顾人口。预计将接受该计划培训的12名高素质人员（HQP）将以科学家或领域的专家加入学术界或行业。