New Machine Learning Approaches for Discrete Optimization

点击翻译按钮获取中文摘要

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.