Hybrid artificial intelligence methods for combinatorial optimization

组合优化（CO）是一个致力于研究和实践能够解决复杂决策问题的算法的领域。这样的问题在许多工业环境中是普遍存在的：减少完成给定生产的资源消耗，为车辆找到最佳路线等。最初，解决这类问题的传统方法是基于搜索程序。最近，随着数据量的激增和计算能力的提高，基于深度学习（DL）的方法越来越受欢迎。在过去的几十年里，深度学习逐渐取代了专家系统来解决许多任务，比如图像识别或自然语言处理。随着基于深度学习的方法的成功，从业者自然会寻求越来越多具有挑战性的应用，并开始考虑组合优化领域。目前，解决组合优化问题的方法有两大类：传统的基于搜索的组合优化方法和新兴的基于学习的组合优化方法。由于学习方法在CO领域是最近才引入的，还不能与传统方法相抗衡。然而，它们有可能提供一些好处。通过利用来自数据和过去决策的知识，一旦对模型进行了预先训练，它们就可以大大加快搜索过程的执行时间。这种混合方法的一个成功案例是著名的AlphaGo Zero算法，它基于搜索程序和深度神经网络，通过自对弈进行训练。在很长一段时间里，对于纯粹的搜索算法来说，围棋仍然是难以解决的问题，而与机器学习的融合使得算法的设计达到了超人的性能。尽管这种杂交的潜力，它还没有如此成功地解决实际的组合优化。这就是为什么寻找一种方法来构建这种混合方法是社区中一个活跃的研究领域。这个研究项目就是在这样的背景下进行的。它提出在人工智能中引入一种基于学习和搜索的混合范式，以解决大型和复杂的组合优化问题。构建这种杂交带来了许多挑战，比如深度学习模型的不精确性质、缺乏泛化、维度的诅咒，或者找到一种正确的方法来表示组合问题作为深度学习模型的输入。这个研究项目将致力于设计创新的解决方案来应对这些挑战。在短期内，我们希望在这一领域进行新的研究，并证实机器学习可以成功地插入搜索过程的想法。从长远来看，我们希望这个项目将有助于提高优化工具的效率，并为更广泛的人群提供便利。

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.