Grant: Discovery Grants Program - Individual
University of Toronto
$24,000.00
New Machine Learning Approaches for Discrete Optimization
EF 2023-24
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2020-06560
Name nom
Khalil, Elias
Department département
Department of Mechanical and Industrial Engineering
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2020
Award amount
24000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Operations research and management science
Research subject en
Génie industriel
Research subject fr
Recherche opérationnelle et science de la gestion
Application title
New Machine Learning Approaches for Discrete Optimization
Keyword
combinatorial optimization; deep learning; discrete optimization; graph neural networks; integer programming; machine learning
Application summary
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.