Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$29,000.00
Hybrid artificial intelligence methods for combinatorial optimization
EF 2023-24
Résumé
Combinatorial optimization (CO) is a field devoted to the study and practice of algorithms that can solve complex decision-making problems. Such problems are ubiquitous in many industrial contexts: reducing the resource consumption for accomplishing a given production, finding optimal routes for vehicles, etc. Initially, traditional methods for tackling such problems were based on a search procedure. More recently, as the abundance of data proliferates and computational power increases, methods based on deep learning (DL), came more and more popular. In the last decades, DL has progressively replaced expert systems to solve numerous tasks, such as in image recognition, or natural language processing. With the success of approaches based on DL, practitioners naturally sought for more and more challenging applications and began to consider the field of combinatorial optimization. Nowadays, there are two families of approaches for tackling combinatorial optimization problems: the traditional ones based on searching and the emerging ones based on learning. As learning methods have been introduced in the CO field only recently, they do not compete yet with the traditional methods. However, they have the potential of offering some benefits. By leveraging knowledge from data and past decisions, they can drastically speed up the execution time of a search procedure once a model has been previously trained. A success story of such a hybrid method is the well-known AlphaGo Zero algorithm, which is based both on a search procedure and a deep neural network, trained by self-play. For a long time, the game of Go remained intractable for pure search algorithms, and the hybridization with machine learning enabled the design of algorithms achieving superhuman performance. Despite the potential of such hybridization, it has not yet been so successful for solving practical combinatorial optimization. This is why finding a way to build such a hybrid method is an active field of research in the community. This research program lies within this context. It proposes to introduce a hybrid paradigm in artificial intelligence, both based on learning and searching, for tackling large and complex combinatorial optimization problems. Building this hybridization raises many challenges, such as the inexact nature of DL models, the lack of generalization, the curse of dimensionality, or finding a correct way to represent a combinatorial problem as input of a DL model. This research program will be dedicated to design innovative solutions to tackle these challenges. In the short term, we expect to enable new research in this field and corroborates the idea that machine learning can be successfully plugged into a search procedure. In the long term, we expect that this program will contribute to the mission of making optimization tools more efficient, and accessible for a large range of people.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2022-03964
Name nom
Cappart, Quentin
Department département
Département de génie informatique et génie logiciel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2022
Award amount
29000
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
2713
Research subject group en
Information technology
Research subject group fr
Algorithms
Research subject en
Technologie de l'information
Research subject fr
Algorithmes
Application title
Hybrid artificial intelligence methods for combinatorial optimization
Keyword
Combinatorial optimization; Constraint programming; Machine learning; Operations research; Reinforcement learning; Search algorithms
Application summary
Combinatorial optimization (CO) is a field devoted to the study and practice of algorithms that can solve complex decision-making problems. Such problems are ubiquitous in many industrial contexts: reducing the resource consumption for accomplishing a given production, finding optimal routes for vehicles, etc. Initially, traditional methods for tackling such problems were based on a search procedure. More recently, as the abundance of data proliferates and computational power increases, methods based on deep learning (DL), came more and more popular. In the last decades, DL has progressively replaced expert systems to solve numerous tasks, such as in image recognition, or natural language processing. With the success of approaches based on DL, practitioners naturally sought for more and more challenging applications and began to consider the field of combinatorial optimization. Nowadays, there are two families of approaches for tackling combinatorial optimization problems: the traditional ones based on searching and the emerging ones based on learning. As learning methods have been introduced in the CO field only recently, they do not compete yet with the traditional methods. However, they have the potential of offering some benefits. By leveraging knowledge from data and past decisions, they can drastically speed up the execution time of a search procedure once a model has been previously trained. A success story of such a hybrid method is the well-known AlphaGo Zero algorithm, which is based both on a search procedure and a deep neural network, trained by self-play. For a long time, the game of Go remained intractable for pure search algorithms, and the hybridization with machine learning enabled the design of algorithms achieving superhuman performance. Despite the potential of such hybridization, it has not yet been so successful for solving practical combinatorial optimization. This is why finding a way to build such a hybrid method is an active field of research in the community. This research program lies within this context. It proposes to introduce a hybrid paradigm in artificial intelligence, both based on learning and searching, for tackling large and complex combinatorial optimization problems. Building this hybridization raises many challenges, such as the inexact nature of DL models, the lack of generalization, the curse of dimensionality, or finding a correct way to represent a combinatorial problem as input of a DL model. This research program will be dedicated to design innovative solutions to tackle these challenges. In the short term, we expect to enable new research in this field and corroborates the idea that machine learning can be successfully plugged into a search procedure. In the long term, we expect that this program will contribute to the mission of making optimization tools more efficient, and accessible for a large range of people.