Quantum annealing (QA) is an optimization process in quantum computing similar to the probabilistic metaheuristic simulated annealing (SA). The QA process involves encoding an optimization problem into an energy landscape, which it then traverses in search for the point of minimal energy representing the global optimal state. In this thesis two different implementations of QA are examined, one run on a binary quadratic model (BQM) and one on a discrete quadratic model (DQM). These are then compared to their traditional counterpart: SA, in terms of performance and accuracy when solving the graph coloring problem (GCP). Regarding performance, the results illustrate how SA outperforms both QA implementations. However, it is apparent that these slower execution times are mostly due to various overhead costs that appear because of limited hardware. When only looking at the quantum annealing part of the process, it is about a hundred times faster than the SA process. When it comes to accuracy, both the DQM-implementation of QA and SA provided results of high quality, whereas the BQM-implementation performed notably worse, both by often not finding the optimal values and by sometimes returning invalid results. / Quantum annealing (QA) är en kvantbaserad optimeringsprocess som liknar den probabilistiska metaheuristiken simulated annealing (SA). QA går ut på att konvertera ett optimeringsproblem till ett energilandskap, som sedan navigeras för att hitta punkten med lägst energi, vilket då motsvarar den optimala lösningen på problemet. I denna uppsats undersöks två olika implementationer av QA: en som använder en binary quadratic model (BQM) och en som använder en discrete quadratic model (DQM). Dessa två implementationerna jämförs med deras traditionella motsvarighet: SA, utifrån både prestanda och korrekthet vid lösning av graffärgningsproblemet (GCP). När det gäller prestanda visar resultaten att SA är snabbare än båda QA implementationerna. Samtidigt är det tydligt att denna prestandaskillnad framförallt beror på diverse förberedelser innan exkueringen startar på kvantdatorn, vilka är krävande på grund av olika hårdvarubegränsningar. Om man endast betraktar kvantprocesserna visar vår studie att QA implementationerna är ungefär hundra gånger snabbare än SA. Gällande korrekthet gav både DQM-implementationen av QA och SA resultat av hög kvalitet medan BQM-implementationen presterade betydligt sämre. Den gjorde detta dels genom att inte skapa optimala resultat och genom att returnera otillåtna lösningar.

Les applications réelles liées aux problèmes de satisfaction partielle de contraintes (PCSP : Partial Constraints Satisfaction Problem) sont de plus en plus nombreuses, ce qui justifie l’intérêt croissant des chercheurs pour cette classe de problèmes. La résolution d’un PCSP revient à affecter des valeurs à toutes ses variables tout en maximisant (ou minimisant) une fonction objectif prédéfinie. Ces problèmes sont NP-difficiles, par conséquent il n’existe aucune approche aussi bien exacte qu’heuristique efficace sur les grandes instances. Pour résoudre efficacement les instances difficiles, une multitude de solutions sont proposées, allant de l’hybridation à l’apprentissage en passant par la décomposition. Dans notre travail, nous nous intéressons à cette dernière proposition, qui consiste à fractionner le problème PCSP en plusieurs sous-problèmes PCSP de tailles raisonnables, puis proposer des algorithmes de résolution pour les problèmes décomposés. Cette approche a pour but de bénéficier de la structure du problème afin d’accélérer sa résolution tout en garantissant des solutions optimales ou sous-optimales. Deux grand axes sont explorés : les approches basées sur la décomposition et celles guidées par la décomposition. Les approches basées sur la décomposition consistent à résoudre séparément les parties difficiles du problème décomposé, puis combiner les solutions partielles obtenues en vue d’atteindre une solution globale du problème d’origine. Les approches guidées par la décomposition consistent à développer des métaheuristiques qui tiennent compte de la structure du problème décomposé. Les algorithmes proposés sont testés et validés sur des instances réelles des problèmes PSCP, comme le problème d’affectation de fréquences et le problème de coloration de graphes / The wide range of potential applications concerned by the resolution of Partial Constraints Satisfaction Problems (PCSP) justifies the growing interest of scientists in this class of problems. Solving a PCSP means searching for values to assign to the decision variables in order to maximize (or minimize) a predefined objective function. These problems are NP-hard, so there isn’t an exact approach nor an efficient heuristic able to provide the optimal solution for large instances. In order to solve effectively the difficult instances, numerous approaches based on hybridization, learning or decomposition are proposed. In the present work, we focus on the latter proposal, which consists in splitting the PCSP into several smaller size PCSPs and we propose some methods to solve the decomposed problem. Two wide axes are explored : the resolution based on the decomposition and the one guided by decomposition. The former solves separately the difficult parts of the decomposed problem (cuts or clusters) and then combines partial solutions obtained in order to achieve a global solution for the original problem. The latter aims at benefiting from the structure of the problem to be decomposed in order to accelerate its resolution while ensuring optimal or near optimal solutions. All the proposed algorithms are tested and validated on the well-known benchmarks of PCSP problems such as Frequency Assignment Problem (FAP) and graph coloring problem

著色問題(graph coloring problem)的研究已行之有年，並衍生出廣泛的實際應用，但還缺乏一般化的著色問題模型。本論文建構一般化的著色問題模型，其目標函數包含顏色成本的固定支出和點著色變動成本。此著色模型為0/1整數線性規畫模型，其限制式含有選點問題(node packing problem)的限制式。我們利用圖中的極大團(maximal clique)所構成的強力限制式，取代原有的選點限制式，縮短求解時間。我們更進一步舉出一個特殊指派問題並將此著色模型應用於此指派問題上。本論文亦針對此指派問題發展了一個演算法來尋找極大團。計算結果顯示極大團限制式對於此著色問題模型的求解有極大的效益。 / The graph coloring problem (GCP) has been studied for a long time and it has a wide variety of applications. A straightforward formulation of graph coloring problem has not been formulated yet. In this paper, we formulate a general GCP model that concerns setup cost and variable cost of different colors. The resulting model is an integer program that involves the packing constraint. The packing constraint in the GCP model can be replaced by the maximal clique constraint in order to shorten the solution time. A special assignment problem is presented which essentially is a GCP model application. An algorithm of finding maximal cliques for this assignment problem is developed. The computational results show the efficiency of maximal clique constraints for the GCP problem.