Résolution de problèmes d'optimisation combinatoire par des approches d'inspiration quantique

Ce mémoire de thèse propose d’évaluer la résolution de problèmes d’optimisation combina- toire NP-difficile par des approches d’inspiration quantique. Au cœur de cette recherche se trouve l’examen du modèle de Ising, une représentation mathématique fondamentale dans la mécanique statistique et la physique quantique. L’objectif est d’explorer comment les prin- cipes de ce modèle de la physique statistique peuvent être exploités pour résoudre efficacement des problèmes complexes, dont la complexité croissante dépasse les capacités des ordinateurs classiques. Ce mémoire contribue ainsi à l’élargissement des horizons de la résolution de pro- blèmes d’optimisation, ouvrant la voie à des applications potentielles dans divers domaines, de la logistique à la conception de médicaments. Les problèmes d’optimisation combinatoires NP-difficile sont nombreux. Dans le cadre de ce mémoire, le point se fera sur les deux problèmes à savoir le TSP et le JSSP utilisés beaucoup en industrie. Le mémoire se concentrera ainsi sur la résolution de ces deux problèmes par des approches d’inspiration quantique. Le recuit simulé, la machine de D-Wave et la machine à bifurcation de Toshiba en font partie. Le mémoire compare aussi les résultats avec d’autres approches dites classiques comme Google-OR et Concorde. Les résultats obtenues par le biais des outils cités précédemment sont de mauvaise qualité comparé aux outils classiques de résolution. Le mémoire vise donc à proposer des méthodes pour améliorer les performances en termes de temps et de qualité de solutions. On a montré qu’avec ces méthodes et approches, les résultats sont allés de mauvais à résultats convaincant. On guise de conclusion, le modèle d’Ising est une approche révolutionnaire pour contrer les problèmes difficiles, mais celui-ci requiert des méthodes de résolution efficaces.

Abstract

This thesis aims to assess the resolution of NP-hard combinatorial optimization problems through quantum-inspired approaches. At the core of this research lies the examination of the Ising model, a fundamental mathematical representation in statistical mechanics and quantum physics. The objective is to explore how the principles of this statistical physics model can be leveraged to efficiently solve complex problems, whose increasing complexity surpasses the capabilities of classical computers. This thesis thus contributes to expanding the horizons of optimization problem-solving, paving the way for potential applications in various fields, from logistics to drug design. Combinatorial optimization problems that fall under the NP-hard category are numerous. In the context of this thesis, the focus will be on two specific problems, namely the Traveling Salesman Problem (TSP) and the Job Shop Scheduling Problem (JSSP), both widely used in the industry. The thesis will primarily explore the resolution of these two problems using quantum-inspired approaches, including simulated annealing, D-Wave quantum machines, and Toshiba’s bifurcation machine. Additionally, the thesis will compare the results obtained from these quantum-inspired methods with those achieved using classical approaches such as Google-OR and Concorde. The results obtained through the aforementioned tools have demonstrated lower quality com- pared to classical solving methods. Therefore, the thesis aims to propose methods to enhance performance in terms of both solution quality and execution time. It has been shown that, with these novel methods and approaches, results have improved from poor to convincing. In conclusion, the Ising model represents a revolutionary approach to tackle challenging problems; however, it requires efficient solving methods to fully harness its potential.