New Machine Learning Approaches for Discrete Optimization

自动化决策是人工智能(AI)的支柱之一。离散优化(DO)解算器是强大的工具，可以为具有数千个变量和约束的问题制定近乎最优的决策。这些优化问题出现在各种领域，如全球散货航运中的海运库存路径、医疗保健中的肾脏交换以及电力系统中的负荷管理。近年来，离散优化问题必须解决的复杂性和频率都有了显著的提高，挑战了现有求解器的能力。另一方面，深度学习的巨大进步使机器学习在具有组合性质的复杂数据的领域中得以采用，例如分子和蛋白质、社会和知识图以及计算机程序的调用图。提出的研究计划旨在建立原则、方法和数据集，以简化通过ML和DL进行离散优化的算法设计过程。有了正确的基于图形的DL模型，由经典算法产生的丰富数据和解成为离散优化求解器性能下一次重大飞跃的关键。考虑海运库存运输路线问题，其中一组船舶将被分配货物和指定的国际航线，以便在延长的时间段内以最低成本满足需求。即使是中等规模的问题实例也不能在几天内通过最先进的混合整数规划(MIP)求解器解决到最优，尽管在过去20年中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.