Note ABES Quantum Computing for Operations Research : A special approach for Project Scheduling Informatique quantique pour la recherche opérationnelle : une approche spéciale pour ordonnancement de projet Ordonnancement Optimisation Incertitude Projet Informatique quantique Recherche opérationnelle Algorithme de Grover Recuit quantique Problèmes quadratiques Scheduling Optimization Uncertainty Project Quantum Computing Operations Research Informatique quantique Recherche opérationnelle Ordonnancement (gestion) Gestion de projets Algorithmes Optimisation combinatoire Le calcul quantique, avec son potentiel profond, a suscité une attention significative ; cependant, son intégration dans la Recherche Opérationnelle (RO) reste naissante. Cette dissertation tente de combler cette lacune en introduisant des algorithmes innovants ancrés dans les principes du calcul quantique pour s'attaquer aux problèmes d'optimisation discrets. La première partie se concentre sur les fondamentaux du calcul quantique et analyse l'algorithme de Grover. Peut-être l'algorithme quantique le plus important, qui est renommé pour son accélération quadratique dans les recherches non structurées. En tirant parti de l'algorithme de Grover, l'étude présente une procédure qui résout efficacement le problème du sac à dos binaire, surmontant des défis souvent négligés dans la littérature sur le calcul quantique.Dans la seconde partie, la thèse affine la performance des algorithmes développés dans le premier chapitre, introduisant deux procédures novatrices : un algorithme hybride de branchement et de bornage et un algorithme d'ascension aléatoire. Ces procédures se révèlent capables d'égaler la performance des algorithmes classiques leaders sur 66000 instances du problème du sac à dos binaire. Notablement, elles étendent leur applicabilité aux problèmes d'optimisation discrets manquant de structures claires, démontrant le potentiel des approches inspirées par le quantique.Dans la troisième partie, l'exploration s'étend à l'examen des limites des algorithmes quantiques existants dans la résolution des problèmes d'optimisation discrets. L'étude évalue de manière critique les algorithmes de comptage quantique, ainsi que les variantes de l'algorithme de Grover telles que la recherche quantique imbriquée, les marches quantiques, et l'algorithme d'amplification d'amplitude, révélant des instances où les contreparties classiques peuvent dominer.Dans la quatrième partie de cette dissertation, nous explorons une avenue prometteuse du calcul quantique pour résoudre des problèmes complexes d'optimisation combinatoire, appelée recuit quantique, et nous l'utilisons spécifiquement pour résoudre le Problème d'Ordonnancement de Projets avec Contraintes de Ressources (RCPSP). Formulant le RCPSP à la fois comme un problème d'Optimisation Binaire Quadratique non contrainte (QUBO) et un modèle Hamiltonien d'Ising, l'étude emploie l'annealeur quantique D-Wave Advantage 6.3 disponible commercialement, appliqué aux instances RCPSP du générateur aléatoire RANGEN1. Les évaluations comparatives contre les solveurs classiques et les algorithmes métaheuristiques affirment le potentiel du recuit quantique, particulièrement pour les instances RCPSP de taille petite à moyenne. Le paysage diversifié de solutions qu'il offre fait du recuit quantique un candidat convaincant pour des algorithmes d'optimisation hybrides, promettant d'améliorer la qualité des solutions.Cette thèse exhaustive contribue à la compréhension théorique et aux applications pratiques du calcul quantique en Recherche Opérationnelle, démontrant son potentiel à révolutionner les méthodologies de résolution de problèmes.Le chapitre cinq de cette thèse explore une nouvelle bibliothèque open-source Python dédiée à l'ordonnancement de projets appelée cheche-pm, qui incorpore et rend disponibles des méthodes d'ordonnancement issues de la littérature pour résoudre le RCPSP et ses variantes. Cette bibliothèque se concentre sur l'apport d'une collection complète de méthodes d'ordonnancement à la fois aux praticiens et aux chercheurs. L'utilisation de cette bibliothèque a été cruciale pour le développement du quatrième chapitre de cette thèse.Enfin, le chapitre six explore l'utilisation d'une implémentation hybride quantique et classique du recuit quantique pour résoudre un cas spécial du problème semi-affectation quadratique QSAP, dans le contexte Quantum computing, with its profound potential, has garnered significant attention; however, its integration into Operations Research (OR) remains nascent. This dissertation attempts to address this gap by introducing innovative algorithms rooted in quantum computing principles to tackle discrete optimization problems. The first part focus on the fundamentals of quantum computing and analyzes Grover's algorithm. Perhaps the most important quantum algorithm that is renowned for its quadratic speedup in unstructured searches. Leveraging Grover's algorithm, the study presents a procedure that effectively solves the binary knapsack problem, overcoming challenges often overlooked in the quantum computing literature.In the second part, the thesis refines the performance of the algorithms developed in the first chapter, introducing two novel procedures a hybrid branch-and-bound algorithm and a random-ascent algorithm. These procedures prove capable of matching the performance of leading classical algorithms across 66000 instances of the binary knapsack problem. Notably, they extend their applicability to discrete optimization problems lacking clear structures, showcasing the potential of quantum-inspired approaches. The refined procedures exhibit efficiency, solving any discrete optimization problem with at most a constant multiplying the square root of n operations.In the third part the exploration extends to scrutinizing existing quantum algorithms' limitations in solving discrete optimization problems. The study critically evaluates quantum counting algorithms, as well as Grover's algorithm variants such as nested quantum search, quantum walks, and the amplitude amplification algorithm, revealing instances where classical counterparts may dominate.In the fourth parth of this dissertation we explore a promising quantum computing avenue for solving complex combinatorial optimization problems, called quantum annealing and we specifically use it to solve the Resource-Constrained Project Scheduling Problem (RCPSP). Formulating RCPSP as both a Quadratic Unconstrained Binary Optimization problem (QUBO) and an Ising Hamiltonian model, the study employs the commercially available D-Wave Advantage 6.3 quantum annealer, applied to RCPSP instances from the Random generator RANGEN1. Comparative assessments against classical solvers and metaheuristic algorithms affirm quantum annealing's potential, particularly for smaller to medium-sized RCPSP instances. The diverse landscape of solutions it offers makes quantum annealing a compelling candidate for hybrid hybrid optimization algorithms, promising to enhance solution quality.This comprehensive thesis contributes to both the theoretical understanding and practical applications of quantum computing in Operations Research, showcasing its potential to revolutionize problem-solving methodologies.Chapter five of this thesis explores a novel python open-source library dedicated to project scheduling called cheche-pm, that incorporates and make available scheduling methods from the literature to solve the RCPSP and it's variants. This library focuses on bringing a comprehensive collectionof scheduling methods to both practitioners and researchers. The use of this library was critical for the development of chapter four of this thesis.Finally Chapter six explores the usage of a hybrid quantum and classical implementation of quantum annealing to solve an special case of the quadratic semi-assignment problem QSAP, in the context of strategic group works. demonstrating the synergy between quantum and classical optimization strategies. Electronic Thesis or Dissertation Text en PDF 28255894 https://pepite-depot.univ-lille.fr/LIBRE/EDSESAM/2024/2024ULILA006.pdf https://theses.hal.science/tel-04967643 https://theses.fr/2024ULILA006/abes https://theses.hal.science/tel-04967643 https://theses.hal.science/tel-04967643 https://theses.hal.science/tel-04967643 Discrete optimization: A quantum revolution Stefan Creemers Luis Fernando Pérez Armas Elsevier en 2024 Text Discrete optimization: Limitations of existing quantum algorithms Stefan Creemers Luis Fernando Pérez Armas en Text Solving the resource constrained project scheduling problem with quantum annealing Luis Fernando Pérez Armas Stefan Creemers Samuel Deleplanque Springer nature en 2024 Text Restricted Min-Norm Semi-Assignment in Group Formation: Quantum and Binary Algorithmic Integration Stefano Nasini Luis Fernando Pérez Armas Elsevier en 2024 Text Pérez Armas Luis Fernando Pérez Armas 1989-07-30 VE 28102765X https://theses.fr/2024ULILA006 2024ULILA006 https://doi.org/10.70675/cf991df2zcbd5z4574z9f45z6f05451dcf70 2024-04-16 Sciences économiques Université de Lille (2022-....) 259265152 Doctorat Docteur es oui oui Creemers Stefan MADS_DIRECTEUR_DE_THESE_1 250387441 Kerstens Kristiaan MADS_PRESIDENT_DU_JURY 157232212 Haven Emmanuel MADS_MEMBRE_DU_JURY_1 169824454 Di Martinelly Christine MADS_MEMBRE_DU_JURY_2 133533980 Belien Jeroen MADS_RAPPORTEUR_1 256328811 Aggoune Riad MADS_RAPPORTEUR_2 073659428 École doctorale Sciences économiques, sociales, de l'aménagement et du management (Lille ; 1992-....) MADS_ECOLE_DOCTORALE_1 14893823X LEM - Lille Économie Management MADS_PARTENAIRE_DE_RECHERCHE_1 161571565 Lille économie management - UMR 9221 MADS_PARTENAIRE_DE_RECHERCHE_2 413157 ddc:330 Creemers Stefan Kerstens Kristiaan Haven Emmanuel Di Martinelly Christine Belien Jeroen Aggoune Riad École doctorale Sciences économiques, sociales, de l'aménagement et du management (Lille ; 1992-....) LEM - Lille Économie Management Lille économie management - UMR 9221 PDF 28255894