New Machine Learning Approaches for Discrete Optimization

用于离散优化的新机器学习方法

• 批准号: RGPIN-2020-06560
• 负责人: Khalil, Elias
• 金额: $ 1.75万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=741314
• 关键词: New; Machine; Learning; Approaches; Discrete

Automated decision-making is one of the pillars of Artificial Intelligence (AI). Discrete Optimization (DO) solvers are powerful tools that can prescribe near-optimal decisions to problems with many thousands of variables and constraints. These optimization problems appear in a variety of domains, such as maritime inventory routing in global bulk shipping, kidney exchanges in healthcare and load management in power systems. In recent years, both the complexity and frequency at which discrete optimization problems must be solved have increased substantially, challenging the capabilities of current solvers. On the other hand, dramatic advances in Deep Learning (DL) have enabled the adoption of Machine Learning (ML) in domains with complex data of combinatorial nature, such as molecules and proteins, social and knowledge graphs, and call graphs of computer programs. The proposed research program aims at establishing principles, methods, and datasets that will streamline the process of algorithm design for discrete optimization through ML and DL. With the right graph-based DL models, the rich data and solutions produced by classical algorithms become key to ushering the next large leap in the performance of discrete optimization solvers. Consider the maritime inventory routing problem, where a set of ships are to be allocated goods and assigned international routes so as to satisfy demand at minimum cost over extended time periods. Even modestly sized instances of this problem cannot be solved to optimality within days by a state-of-the-art Mixed Integer Programming (MIP) solver, despite substantial advances in MIP solving in the past two decades. On the other hand, many emerging applications require solving similar optimization problems very frequently. For example, in ride-sharing services, drivers must be dynamically assigned to riders. While the drivers, riders, their locations and request times vary, the underlying mathematical model for this assignment problem does not, giving rise to similar optimization problems that must be solved in near real-time. Solvers, however, process each new problem instance de novo, even when they have already encountered many similar instances in the past. Both of these game-changing aspects-increased complexity and high frequency-bring about a wealth of data that goes mostly unexploited in the optimization process. Highly complex problems require many iterations, thus generating solving traces that could inform subsequent iterations. High-frequency problems offer data in the form of multiple instances of the same mathematical problem, which could be leveraged to produce an algorithm that is efficient for that distribution of instances. We will improve exact (tree search) and heuristic algorithms with data-driven ML approaches across three complementary thrusts: 1) Deep Graph Embeddings for DO Problems; 2) Sample-Efficient Learning Methods for DO; 3) New Datasets and Domains for Learning in DO.

自动决策是人工智能（AI）的支柱之一。离散优化（DO）求解器是一种强大的工具，可以为具有数千个变量和约束的问题提供接近最优的决策。这些优化问题出现在各种领域，如全球散装运输中的海运库存路由，医疗保健中的肾脏交换和电力系统中的负载管理。近年来，离散优化问题必须解决的复杂性和频率都大幅增加，对当前求解器的能力提出了挑战。另一方面，深度学习（DL）的巨大进步使机器学习（ML）能够在具有组合性质的复杂数据的领域中采用，例如分子和蛋白质，社会和知识图以及计算机程序的调用图。拟议的研究计划旨在建立原则，方法和数据集，以简化通过ML和DL进行离散优化的算法设计过程。通过正确的基于图形的DL模型，经典算法产生的丰富数据和解决方案成为离散优化求解器性能下一次飞跃的关键。考虑海运库存路由问题，其中一组船舶将被分配货物和指定的国际航线，以便在延长的时间段内以最小的成本满足需求。即使是中等规模的情况下，这个问题不能解决的最佳状态的最先进的混合编程（MIP）求解器在几天内，尽管MIP解决在过去的二十年中取得了重大进展。另一方面，许多新兴的应用程序需要解决类似的优化问题非常频繁。例如，在拼车服务中，司机必须动态分配给乘客。虽然司机、乘客、他们的位置和请求时间不同，但这个分配问题的基本数学模型却不同，这就产生了类似的优化问题，必须近实时地解决。然而，求解器重新处理每个新的问题实例，即使他们在过去已经遇到过许多类似的实例。这两个改变游戏规则的方面增加的复杂性和高频率带来了大量的数据，这些数据在优化过程中大多未被利用。高度复杂的问题需要多次迭代，从而生成可以通知后续迭代的解决轨迹。高频问题以同一数学问题的多个实例的形式提供数据，可以利用这些数据来生成对该实例分布有效的算法。我们将通过数据驱动的ML方法在三个互补的方面改进精确（树搜索）和启发式算法：1）用于DO问题的深度图嵌入; 2）用于DO的样本有效学习方法; 3）用于DO学习的新数据集和域。