Hybrid artificial intelligence methods for combinatorial optimization

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

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.