Dans cette thèse, nous avons présenté un nouvel algorithme hybride (HA) pour la résolution du problème (UQP). Cet algorithme est basé sur la combinaison d'un bloc de cinq procédures spéciales et de la méthode du recuit simulé. Nos procédures sont très efficaces et rapides, mais malheureusement, parfois elles sont bloquées par un minimum local. Pour surmonter cet inconvénient, nous les avons combinées avec un algorithme de recuit simulé. Ensuite, nous avons répété ces procédures plusieurs fois pour obtenir la meilleure solution en utilisant notre algorithme hybride.Nous avons remarqué que l'écart entre la solution trouvée par (HA) et le logiciel CPLEX est très faible, ce résultat implique l'efficacité de notre stratégie. Par ailleurs, nous avons intégré notre méthode hybride à un problème de relaxation semi-définie du (UQP) dans le cadre d'une stratégie de branch and bound. Pour faciliter la résolution du (UQP), nous suggérons d'appliquer des critères de fixation afin de réduire la taille du problème et d'accélérer l'obtention d'une solution exacte. La qualité de la borne inférieure trouvée par notre code (QPTOSDP) est très bonne, mais le temps d'exécution augmente avec la taille du problème. Les résultats numériques prouvent l'exactitude de notre solution optimale et l'efficacité et la robustesse de notre approche.Nous avons étendu les critères de fixation pour le problème (QP), ce qui permet, dans certains cas, de réduire la dimension du problème, voire de le résoudre entièrement en appliquant une boucle de répétition fondée sur ces critères.
Dans cette thèse, nous avons présenté un nouvel algorithme hybride (HA) pour la résolution du problème (UQP). Cet algorithme est basé sur la combinaison d'un bloc de cinq procédures spéciales et de la méthode du recuit simulé. Nos procédures sont très efficaces et rapides, mais malheureusement, parfois elles sont bloquées par un minimum local. Pour surmonter cet inconvénient, nous les avons combinées avec un algorithme de recuit simulé. Ensuite, nous avons répété ces procédures plusieurs fois pour obtenir la meilleure solution en utilisant notre algorithme hybride.Nous avons remarqué que l'écart entre la solution trouvée par (HA) et le logiciel CPLEX est très faible, ce résultat implique l'efficacité de notre stratégie. Par ailleurs, nous avons intégré notre méthode hybride à un problème de relaxation semi-définie du (UQP) dans le cadre d'une stratégie de branch and bound. Pour faciliter la résolution du (UQP), nous suggérons d'appliquer des critères de fixation afin de réduire la taille du problème et d'accélérer l'obtention d'une solution exacte. La qualité de la borne inférieure trouvée par notre code (QPTOSDP) est très bonne, mais le temps d'exécution augmente avec la taille du problème. Les résultats numériques prouvent l'exactitude de notre solution optimale et l'efficacité et la robustesse de notre approche.Nous avons étendu les critères de fixation pour le problème (QP), ce qui permet, dans certains cas, de réduire la dimension du problème, voire de le résoudre entièrement en appliquant une boucle de répétition fondée sur ces critères.
Dans cette thèse, nous avons présenté un nouvel algorithme hybride (HA) pour la résolution du problème (UQP). Cet algorithme est basé sur la combinaison d'un bloc de cinq procédures spéciales et de la méthode du recuit simulé. Nos procédures sont très efficaces et rapides, mais malheureusement, parfois elles sont bloquées par un minimum local. Pour surmonter cet inconvénient, nous les avons combinées avec un algorithme de recuit simulé. Ensuite, nous avons répété ces procédures plusieurs fois pour obtenir la meilleure solution en utilisant notre algorithme hybride.Nous avons remarqué que l'écart entre la solution trouvée par (HA) et le logiciel CPLEX est très faible, ce résultat implique l'efficacité de notre stratégie. Par ailleurs, nous avons intégré notre méthode hybride à un problème de relaxation semi-définie du (UQP) dans le cadre d'une stratégie de branch and bound. Pour faciliter la résolution du (UQP), nous suggérons d'appliquer des critères de fixation afin de réduire la taille du problème et d'accélérer l'obtention d'une solution exacte. La qualité de la borne inférieure trouvée par notre code (QPTOSDP) est très bonne, mais le temps d'exécution augmente avec la taille du problème. Les résultats numériques prouvent l'exactitude de notre solution optimale et l'efficacité et la robustesse de notre approche.Nous avons étendu les critères de fixation pour le problème (QP), ce qui permet, dans certains cas, de réduire la dimension du problème, voire de le résoudre entièrement en appliquant une boucle de répétition fondée sur ces critères.
Le domaine du management de l'énergie implique de nombreux problèmes d'optimisation combinatoire connus pour être difficiles. L'émergence des ordinateurs quantiques suggère de nouvelles approches pour ces problèmes. Pour les machines du futur proche, les heuristiques quantiques variationnelles telles que QAOA, qui peuvent tirer parti de la puissance de calcul des ordinateurs quantiques imparfaits, sont particulièrement prometteuses. Nous explorons le potentiel des algorithmes quantiques variationnels pour des problèmes d'optimisation issus du domaine de "smart charging" des véhicules électriques. Nous considérons deux problèmes inspirés de cas d'utilisation réels. Dans le premier problème, modélisé par Max-K-Cut, nous cherchons à planifier un ensemble de charges avec priorités sur plusieurs stations tout en minimisant le temps de completion pondéré. Dans le deuxième problème, modélisé par Maximum Independent Set, nous cherchons à maximiser le nombre de demandes de charge satisfaites sur une seule station tout en respectant les conflits entre les demandes. Pour les deux problèmes, nous développons un protocole expérimental spécifiant l'encodage et la routine d'optimisation des paramètres. Nos expériences numériques confirment l'intérêt des heuristiques quantiques pour ces problèmes ainsi que la qualité de notre protocole expérimental. Afin d'étendre l'applicabilité des heuristiques quantiques au-delà de QUBO, nous introduisons une nouvelle approche hybride qui intègre des routines quantiques dans l'algorithme classique de Branch & Price pour les programmes linéaires en nombres entiers. Nous testons cette approche sur un problème de smart charging qui se modélise comme problème de coloration de graphe. Nos résultats numériques affirment le potentiel de l'approche hybride tout en révélant la dépendance considérable du gain de performance sur l'instance particulière du problème. Les parties importants des algorithmes variationnels peuvent être représentés sous forme de diagrammes ZX. Nous démontrons comment les règles de réécriture du ZX-calculus peuvent être utilisées pour dériver la formule analytique de l'énergie moyenne d'un modèle d'Ising dans un état QAOA with depth 1. De plus, nous contribuons à l'exploration théorique des algorithmes variationnels en étendant le ZX-calcul avec addition et différenciation de ZX-diagrammes. Notre procédure inductive pour l'addition est entièrement graphique. Pour la différenciation, nous suggérons deux approches. La première approche est inductive, elle s'appuie sur notre procédure d'addition pour représenter explicitement les règles du produit. La deuxième approche est résumée dans deux formules qui sont dérivées de la forme factorisée des diagrammes paramétrés.
Le probleme de la minimisation d'une fonction pseudo-booleenne quadratique sous une contrainte lineaire est np-difficile. Par consequent, l'obtention de bornes inferieures est importante. Nous avons etudie differentes methodes pour calculer des bornes inferieures de la solution optimale et nous montrons que le calcul de ces bornes revient a la resolution de programmes lineaires continus. La principale originalite de nos travaux, est qu'ils generalisent les bornes proposees pour le probleme de la minimisation d'une fonction pseudo-booleenne quadratique sans contraintes. Nous avons ensuite applique le calcul des bornes proposees a des problemes particuliers ; la bipartition minimale d'un graphe, l'ensemble stable de cardinal maximal d'un graphe et le sac a dos quadratique. Pour chaque probleme nous avons mis en evidence des proprietes interessantes qui permettent de simplifier le calcul des bornes et des coupes qui permettent d'ameliorer la qualite des bornes proposees. En outre, pour reduire le temps de resolution des programmes lineaires continus consideres, nous avons elabore une methode de coupes qui permet de resoudre des programmes lineaires continus de maniere approchee. Enfin, pour chaque probleme particulier, nous avons integre notre methode de coupes dans un algorithme de resolution exacte (branch and cut). Nous nous sommes egalement interesse a un probleme d'optimisation lie a l'architecture des futurs reseaux numeriques urbains. Le probleme est de determiner une topologie en anneau de cout minimal qui respecte un certain nombre de contraintes. Nous avons modelise ce probleme a l'aide de la programmation mathematique et montre qu'une methode de resolution fondee sur la programmation lineaire en nombres entiers et les methodes de coupes permet de traiter des problemes reels avec un temps de calcul raisonnable.
Un probleme quadratique en variables binaires est un probleme d'optimisation en variables binaires consistant a minimiser une fonction objectif quadratique sous des contraintes lineaires. Dans cas general, c'est un probleme dificile a resoudre de maniere exacte (NP- difficile), trouvant de nombreuses applications pratiques. La resolution exacte du probleme passe par determination de bornes inferieures qu'il convient d'integrer dans des schemas de separation et evaluation progressive (ou Branch-and-Bound). Plusieurs techniques, allant de programmation semi-definie positive a l'optimisation globale, sont utilisees pour determiner ces bornes. Nous nous sommes particulierement interesses aux methodes lagrangiennes et aux techniques de linearisation. Nous avons traite dans cette these deux instances particulieres du probleme : la bipolarisation de graphes avec contrainte de cardinalite et le probleme quadratique en variables binaires sans contrainte. Pour bipartition de graphes, nous avons propose une demarche hybride melant relaxation lagrangienne et linearisation de probleme. Les tests numeriques, issus de l'algorithme resultant, ont montre des ameliorations significatives par rapport a certaines techniques existantes. Pour probleme quadratique en variables binaires sans contrainte, des etudes sur les techniques de linearisation ont ete effectuees. Elles consistent a remplacer fonction objectif quadratique par une forme lineaire, grâce a l'ajout de variables permettant de remplacer les parties quadratiques de fonction. L'ajout de ces variables entrainent [sic] aussi l'ajout de contraintes visant a s'assurer de validite du remplacement. Apres etude et tests des linearisations existantes, nous unifions ces techniques dans un schema general de linearisation. De nouveaux modeles ont, grâce a ce schema , vu jour et ameliorent significativement les resultats numeriques des formulations lineaires precedentes
Les codes binaires à matrices creuses (Low-Density Parity-Check, LDPC) et les turbo-codes ont une capacité s’approchant de la limite de Shannon pour des trames de grande taille. Cependant, ces codes ont le désavantage d’être moins efficaces pour les faibles tailles. De plus, l’association de codes binaires avec des modulations d’ordre élevé oblige à une étape de marginalisation pour passer d’un symbole aux fiabilités des bits associés à ce symbole. Ce calcul s’accompagne d’une perte d’information qui peut être récupérée par démodulation itérative au prix d’une plus grande complexité. Les codes LDPC définis sur des corps de Galois d’ordre q > 2 permettent de résoudre ces problèmes. Toutefois, lesdécodeurs optimaux associés ont une complexité très importante qui rend leur utilisation problématique.L’objectif de cette thèse est de valoriser les codes LDPC non binaires en proposant d’une part une architecture d’un décodeur à complexité réduite et en montrant d’autre part l’intérêt de les associer à des modulations d’ordre élevé. Dans la première partie de notre thèse, nous proposons de simplifier l’algorithme de décodage Extended Min-Sum (EMS) en considérant un nombre limité n_α << n_m des fiabilités intrinsèques lors de la mise à jour des messages par les nœuds de variable. Cette approche permet de réduire la taille de la mémoire dédiée au stockage des messages intrinsèques. De plus, pour améliorer l’effcacité des nœuds de parité nous proposons une variante simplifiée de l’algorithme L-Bubble Check et l’architecture associée. Enfin, nous montrons par l’intermédiaire d’un prototype sur une carte FPGA (Field Programmable Gate Array) que notre décodeur possède une faible complexité en le comparant avec un ancien décodeur EMS conçu par notre laboratoire de recherche dans le cadre du projet européen DAVINCI. Dans la deuxième partie, nous étudions l’association des codes LDPC non binaires avec une modulation par décalage cyclique de code (Cyclic Code-shift Keying, CCSK) de même ordre. Nous avons choisi cette modulation pour ses propriétés qui permettent de réduire la complexité du démodulateur. En effet, nous montrons qu’il est possible dans le cas d’un système de transmission mono-porteuse avec préfixe cyclique de fusionner le démodulateur et l’égaliseur dans un même bloc comportant une seule transformée de Fourier rapide et une seule transformée de Fourier rapide inverse. Les simulations montrent que ce système possède des performances comparables à un système de transmission multiporteuses de type OFDM (Orthogonal Frequency-Division Multiplexing). Elles montrent aussi que la modulation CCSK donne des performances meilleures que la modulation de Hadamard dans un canal en environnement intérieur sélectif en fréquence. Enfin, les simulations montrent que les codes LDPC non binaires sont nettement plus effcaces avec la modulation CCSK que les codes LDPC binaires même en considérant une démodulation itérative.
Les ordinateurs quantiques actuels sont encore loin de ressembler à l'image idéalisée que pouvaient se faire les pionniers de l'algorithmie quantique : ils sont de taille limitée (ayant au mieux quelques centaines de qubits) et ont un mauvais rapport signal/bruit. Ces ordinateurs sont appelés ordinateurs quantiques bruités de taille intermédiaire (NISQ). Cela ne signifie pas pour autant qu'ils sont seulement des prototypes sans utilité pratique. Les ordinateurs NISQ resteront majoritaires jusqu'au développement de machines employant des méthodes de correction d'erreurs (FTQC). De ce fait, il serait de première importance de faire des investigations sur le type de calcul et d'algorithme qu'il est possible de mettre en oeuvre sur ces machines, en particulier dans le cadre des problèmes d'optimisation basés sur des algorithmes hybrides où l'ordinateur NISQ pourrait être utilisé comme accélérateur de calcul et intégré à un processus classique plus large. L'implémentation d'algorithmes NISQ nécessite des optimisations proches du matériel afin de tirer le meilleur parti de ces nouvelles technologies. Cela inclut de potentielles optimisations à différents niveaux de la pile logicielle quantique allant de la formulation du problème d'optimisation au raffinement des solutions retournées par l'ordinateur quantique, en passant par l'amélioration de la compilation dédiée en fonction de la puce utilisée. Dans cette thèse, nous proposons d'évaluer les limites des annealers quantiques (QA) tels que ceux commercialisés par l'entreprise D-Wave. Cette technologie exploite l'effet tunnel durant son processus d'annealing mais rencontre des difficultés pour trouver des solutions de bonne qualité pour des problèmes d'optimisation binaires quadratiques non contraints (QUBO). Un problème contraint peut être formulé en QUBO en traduisant les contraintes sous forme de pénalités ajoutées à la fonction de coût. Dans le cas du problème de partitionnement de graphe équilibré, la contrainte d'équilibrage est transformée sous forme de pénalités et tend à densifier le problème QUBO. Il est alors difficile de trouver une représentation de ce problème sur les puces quantiques faiblement connectées. C'est ici que la compilation joue un rôle clef mais reste difficile à réaliser. Nous avons développé un cadriciel afin d'évaluer la performance des annealers quantiques basés sur un ensemble d'instances dont la représentation sur puce quantique est optimale. Malgré la bonne qualité de cette représentation, l'annealer quantique est peu compétitif dans la résolution de problèmes d'optimisation par rapport à des méthodes de résolution classiques de l'état de l'art. Nous présentons également un second outil permettant de faciliter la comparaison d'études de performances basées sur des problèmes d'optimisation. Cet outil permet d'évaluer la diversité des propriétés des instances utilisées dans le cadre d'une évaluation de performance. Il permet ainsi d'évaluer le niveau de confiance pouvant être accordé à une étude de performance. Enfin, l'étape de compilation des annealers quantiques permet d'associer un qubit logique à un ensemble de qubits physiques fortement liés. Le bon paramétrage de la force de couplage entre ces qubits physiques permet d'accroître considérablement la performance de l'annealer quantique. Nous introduisons une méthode de recherche dichotomique afin de paramétrer efficacement cette force de couplage.