Hybrid artificial intelligence methods for combinatorial optimization

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

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.