New Machine Learning Approaches for Discrete Optimization

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

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.