Combinatorial optimization include such tasks as finding the quickest route to work, scheduling jobs to specialists, and placing bus stops so as to minimize commuter times. We consider problems where one is given a collection of constraints with the objective of finding an assignment satisfying as many constraints as possible, also known as Constraint Satisfaction Problems (CSPs). Most CSPs are NP-hard to solve optimally and we turn to approximations - a solution is said to be a factor-c approximation if its satisfies at least c times the optimal number of constraints. This thesis presents new results on the approximation limits of CSPs in various settings. In ordering CSPs, one is given constraints which specify the relative order of items, and the objective is order the items so as to satisfy as many constraints as possible. We give improved approximation hardness results for two classical problems: it is NP-hard to approximate Maximum Acyclic Subgraph with a factor better than 14/15 and Maximum Betweenness with a factor better than 1/2. We present ordering problems which are NP-hard to approximate better than random assignments, and that there are ordering problems arbitrarily hard to approximate. Next, Gaussian elimination can efficiently find exact solutions for satisfiable collections of so-called parity constraints. We show that whenever constraints accept at least one assignment in addition to a parity, then the problem is NP-hard to approximate better than random assignments. Finally, we study the uselessness property which basically states that if one is given a collection where almost all constraints are simultaneously satisfiable and one is permitted to relax the constraints to accept or reject additional assignments, then it is still NP-hard to find solutions noticeably better than random assignments. We consider the setting where all variables appear unnegated and provide the first examples of non-trivially useless predicates assuming only P != NP. / Kombinatoriska optimering inkluderar naturliga uppgifter såsom att hitta den snabbaste vägen till sitt arbetet, att schemalägga jobb hos specialister, eller att placera hållplatser för att minimera resenärers restid.Vi begränsar vi oss till de problem i vilket man ges en samling vilkor på variablermed målet att hitta en tilldelning av variablerna uppfyllandes så många som möjligt av vilkoren;så kallade Vilkorsuppfyllningsproblem (eng: Constraint Satisfaction Problems, CSPs).De flesta CSPs är NP-svåra att lösa optimalt och vi beaktar istället approximationer. Specifikt kallas, för 0 &lt;= c &lt;= 1, en lösning för en faktor-c approximation om antalet vilkor uppfyllda av lösningen är minst cgånger det största antalet uppfyllda av någon läsning. Denna avhandling består av tre artiklar som presenterar nya resultat begränsande hurpass väl man kan approximera CSPs i diverse situationer.För paritetsvilkor är en samling konsistenta vilkor enkla att lösa genom Gausselimination. Vi visar att för samtliga vilkor som uppfylls av en paritet och åtminstonde en ytterliggare tilldelning så är det inte bara NP-svårt at lösa utan till och med att ge en icke-trivial approximation.Oanvändarbarhet är en stark svårighetsegenskap som i princip säger att det är NP-svårt att ge icke-triviala approximationer även när man gemensamt för alla vilkor får ändra vad som uppfyller dem eller inte. Vi ger de första exemplen på icke-trivialt oanvändbara vilkor utan negationer betingat endast på P != NP.Vi visar på approximerbarhet för diverse ordningsvilorsproblem. I dessa ges man vilkor på hur objekt ska vara ordnade relativt varandra och målet är att hitta en ordning som uppfyller så många av vilkoren som möjligt. Vi ger bättre svårighetsresultat för de två mest välkända ordningsproblem, visar att det finns problem där det är NP-svårt att approximera bättre än triviala strategier, och att det finns ordningsproblem där godtyckligt dåliga approximationsgarantier är NP-svåra. / <p>NADA är en delad institution mellan SU och KTH där senare nu kallar den CSC.</p> / ApproxNP

This master's thesis investigates the application of Graph Neural Networks (GNNs) to address scalability challenges in combinatorial optimization, with a primary focus on the minimum Total Dominating set Problem (TDP) and additionally the related Carrier Scheduling Problem (CSP) in networks of Internet of Things. The research identifies the NP-hard nature of these problems as a fundamental challenge and addresses how to improve predictions on input graphs of sizes much larger than seen during training phase. Further, the thesis explores the instability in such scalability when leveraging GNNs for TDP and CSP. Two primary measures to counter this scalability problem are proposed and tested: incorporating node degree as an additional feature and modifying the attention mechanism in GNNs. Results indicate that these countermeasures show promise in addressing scalability issues in TDP, with node degree inclusion demonstrating overall performance improvements while the modified attention mechanism presents a nuanced outcome with some metrics improved at the cost of others. Application of these methods to CSP yields bleak results, evincing the challenges of scalability in more complex problem domains. The thesis contributes by detecting and addressing scalability challenges in combinatorial optimization using GNNs and provides insights for further research in refining methodologies for real-world applications. / Denna masteruppsats undersöker tillämpningen av Grafiska Neurala Nätverk (GNN) för att hantera utmaningar inom skalbarhet vid kombinatorisk optimering, med ett primärt fokus på minimum Total Dominating set Problem (TDP) samt även det relaterade Carrier Scheduling Problem (CSP) i nätverk inom Internet of Things. Studien identifierar den NP-svåra karaktären av dessa problem som en grundläggande utmaning och lyfter hur man kan förbättra prediktioner på indatagrafer av storlekar som är mycket större än vad man sett under träningsfasen. Vidare utforskar uppsatsen instabiliteten i sådan skalbarhet när man utnyttjar GNN för TDP och CSP. Två primära åtgärder mot detta skalbarhetsproblem föreslås och testas: inkorporering av nodgrad som ett extra attribut och modifiering av attention-mekanismer i GNN. Resultaten indikerar att dessa motåtgärder har potential för att angripa skalbarhetsproblem i TDP, där inkludering av nodgrad ger övergripande prestandaförbättringar medan den modifierade attention-mekanismen ger ett mer tvetydigt resultat med vissa mätvärden förbättrade på bekostnad av andra. Tillämpning av dessa metoder på CSP ger svaga resultat, vilket antyder om utmaningarna med skalbarhet i mer komplexa problemdomäner. Uppsatsen bidrar genom att upptäcka och adressera skalbarhetsutmaningar i kombinatorisk optimering med hjälp av GNN och ger insikter för vidare forskning i att förfina metoder för verkliga tillämpningar.

In route planning the goal is to obtain the best route between a set of locations, which becomes a very complex task as the number of locations increase. This study will consider the problem of transfer bus route planning and examines the feasibility of applying a reinforcement learning method in this specific real-world context. In recent research, reinforcement learning methods have emerged as a promising alternative to classical optimization algorithms when solving similar problems. This due to their positive properties in terms of scalability and generalization. However, the majority of said research has been performed on strictly theoretical problems, not using real-world data. This study implements an existing reinforcement learning model and adapts it to fit the realms of transfer bus route planning. The model is trained to generate optimized routes in terms of time and cost consumption. Then, routes generated by the trained model are evaluated by comparing them to corresponding manually planned routes. The reinforcement learning model produces routes that outperforms manually planned routes with regards to both examined metrics. However, due to delimitations and assumptions made during the implementation, the explicit differences in consumptions are considered promising but cannot be taken as definite results. The main finding is the overarching behavior of the model, implying a proof of concept; reinforcement learning models are usable tools in the context of real-world transfer bus route planning. / Inom ruttplanering är målet att erhålla den bästa färdvägen mellan en uppsättning platser, vilket blir en mycket komplicerad uppgift i takt med att antalet platser ökar. Denna studie kommer att behandla problemet gällande ruttplanering av transferbussar och undersöker genomförbarheten av att tillämpa en förstärkningsinlärningsmetod på detta verkliga problem. I nutida forskning har förstärkningsinlärningsmetoder framträtt som ett lovande alternativ till klassiska optimeringsalgoritmer för lösandet av liknande problem. Detta på grund utav deras positiva egenskaper gällande skalbarhet och generalisering. Emellertid har majoriteten av den nämnda forskningen utförts på strikt teoretiska problem. Denna studie implementerar en befintlig förstärkningsinlärningsmodell och anpassar den till att passa problemet med ruttplanering av transferbussar. Modellen tränas för att generera optimerade rutter, gällande tids- och kostnadskonsumtion. Därefter utvärderas rutterna, som genererats av den tränade modellen, mot motsvarande  manuellt planerade rutter. Förstärkningsinlärningsmodellen producerar rutter som överträffar de manuellt planerade rutterna med avseende på de båda undersökta mätvärdena. På grund av avgränsningar och antagandet som gjorts under implementeringen anses emellertid de explicita konsumtionsskillnaderna vara lovande men kan inte ses som definitiva resultat. Huvudfyndet är modellens övergripande beteende, vilket antyder en konceptvalidering; förstärkningsinlärningsmodeller är användbara som verktyg i sammanhanget gällande verklig ruttplanering av transferbussar.

Recently, Udwani defined a new class of set functions under monotonicity and subadditivity, called submodular order functions, which is a subfamily of submodular functions. Informally, the submodular order function admits a very limited form of submodularity which is defined over a specific permutation of the ground set. His work pointed out the intriguing connection between streaming submodular maximization and submodular order maximization. Inspired by a 0.25-approximation streaming algorithm for maximizing a monotone submodular function subject to a matroid constraint, Udwani gave a 0.25-approximation algorithm for submodular order functions maximization subject to a matroid constraint. Based on the above results, we would like to explore further in which cases it is feasible to generalize from streaming submodular maximization algorithms to submodular order maximization algorithms. As a more general constraint than matroid, p-matchoid is a collection of p matroids with each matroid defined on some subsets of the ground set. Related work gave a 1/4p-approximation streaming algorithm for monotone submodular functions maximization under a p-matchoid constraint. Inspired by the above algorithms and the intriguing connection, we used some techniques to try to generalize several streaming algorithms for submodular functions to the offline algorithms for submodular order functions, including interleaved partitions and incremental values. Assuming that the objective function f is subadditive and non-negative, we gave a 1/4p-approximation algorithm for monotone submodular order maximization to a p-matchoid constraint. In addition, we summarize the failures of other cases. / Nyligen definierade Udwani en ny klass av mängdfunktioner under monotonicitet och subadditivitet, som kallas submodulära ordningsfunktioner och som är en underfamilj av submodulära funktioner. Informellt sett medger den submodulära ordningsfunktionen en mycket begränsad form av submodularitet som är definierad över en specifik permutation av grundmängden. Hans arbete pekade på det spännande sambandet mellan strömmande submodulär maximering och submodulär ordermaximering. Inspirerad av en strömningsalgoritm med 0.25-approximation för maximering av en monoton submodulär funktion som är föremål för en matroidbegränsning, gav Udwani en algoritm med 0.25-approximation för maximering av submodulära ordningsfunktioner som är föremål för en matroidbegränsning. Baserat på ovanstående resultat skulle vi vilja utforska ytterligare i vilka fall det är möjligt att generalisera från algoritmer för strömning av submodulära maximeringsfunktioner till algoritmer för maximering av submodulära orderfunktioner. Som en mer allmän begränsning än matroid är p-matchoid en samling av p matroider där varje matroid definieras på vissa delmängder av grundmängden. Relaterade arbeten gav en strömmingsalgoritm med 1/4p-tillnärmning för monoton submodulär funktionsmaximering under en p-matchoid-begränsning. Inspirerade av ovanstående algoritmer och det spännande sambandet använde vi vissa tekniker för att försöka generalisera flera strömningsalgoritmer för submodulära funktioner till offline-algoritmer för submodulära ordningsfunktioner, inklusive interleaved partitions och inkrementella värden. Under förutsättning att målfunktionen f är subadditiv och icke-negativ gav vi en algoritm för 1/4p-tillnärmning för monoton submodulär ordermaximering till ett p-matchoid-begränsningsvillkor. Dessutom sammanfattar vi misslyckanden i andra fall.

The Physical Uplink Control Channel (PUCCH), which is mainly used to transmit Uplink Control Information (UCI), is a key component to enable the 5G NR system. Compared to LTE, NR specifies a more flexible PUCCH structure to support various applications and use cases. In the literature, however, an optimized solution that exploits those degrees of freedom is missing and fixed-heuristic solutions are just implemented in current 5G networks. Consequently, the predefined PUCCH format configuration is inefficient because it proposes a one-size-fits-all solution. In short, the number of symbols dedicated to PUCCH resources are often pre-determined and fixed without considering the UE’s specific needs and requirements. Failure to exploit the diversity of PUCCH format configurations and sticking to the one-size-fits-all solution, translates into a poor PUCCH resource allocation in the physical grid. To overcome this, a solution is presented by introducing a more efficient PUCCH re-distribution algorithm that exploits the same Physical Resource Block (PRB) domain. This leads into a combinatorial optimization problem with the objective of minimizing the PRBs utilization while maximizing the number of resources allocated and, in essence, the number of UEs “served”. For this purpose, we utilize a Monte Carlo Tree Search (MCTS) method to find the optimal puzzle on the grid, which offers clear advantages in search time benchmarked against an exhaustive search method. A wide variety of cases and scenario-dependent solutions are allowed using this puzzling technique. Overall results indicate that the optimal solutions devised by MCTS in conjunction with the new resource allocation algorithm bring substantial improvement compared to the one-size-fits-all baseline. In particular, this novel implementation, nonexistent to date in the 3GPP standard, reduces the dedicated PUCCH resource region by 1=6 without sacrificing any user’s allocation, while reusing the remaining PRBs (an increase of up to 11:36%) for the UL data channel or PUSCH. As a future work, we expect to observe similar improvements in higher layers metrics and KPIs, once link-level reception details are implemented and simulated for UL control channels based on our resource allocation solution. / PUCCH, som huvudsakligen används för att överföra UCI, är en nyckelkomponent för att möjliggöra 5G NR-systemet. Jämfört med LTE specificerar NR en mer flexibel PUCCH-struktur för att stödja olika tillämpningar och användningsfall. I litteraturen saknas dock en optimerad lösning som utnyttjar dessa frihetsgrader, och fasta heuristiska lösningar har bara implementerats i nuvarande 5G-nät. Följaktligen är den fördefinierade konfigurationen av PUCCH-formatet ineffektiv eftersom den föreslår en lösning som passar alla. Kort sagt, antalet symboler som är avsedda för PUCCH-resurser är ofta förutbestämda och fastställda utan att man tar hänsyn till UE:s specifika behov och krav. Om man inte drar nytta av den mångfald av PUCCH-formatkonfigurationer och håller sig till en lösning som passar alla, kommer det att leda till en dålig PUCCH-resursallokering i det fysiska resursnätet. För att lösa detta presenteras en lösning genom att införa en effektivare algoritm för omfördelning av PUCCH som utnyttjar samma PRB-domän. Detta leder till ett kombinatoriskt optimeringsproblem med målet att minimera PRB-utnyttjandet och samtidigt maximera antalet tilldelade resurser och, i huvudsak, antalet betjänadeänvändare. För detta ändamål använder vi en MCTS-metod för att hitta det optimala pusslet på rutnätet, vilket ger klara fördelar i söktid jämfört med en uttömmande sökmetod. En mängd olika fall och scenarioberoende lösningar tillåts med hjälp av denna pusselteknik. De övergripande resultaten visar att de optimala lösningarna som MCTS har tagit fram tillsammans med den nya resursfördelningsalgoritmen ger avsevärda förbättringar jämfört med den grundläggande lösningen med en enda lösning som passar alla. Denna nya implementering, som hittills inte funnits i 3GPP-standarden, minskar det dedikerade PUCCH-resursområdet med 1=6 utan att offra någon användarallokering, samtidigt som de återstående PRB:erna återanvänds (en ökning med upp till 11:36%) för UL-datakanalen eller PUSCH. Som ett framtida arbete förväntar vi oss att observera liknande förbättringar i mätvärden och KPI:er på högre nivåer, när mottagningsdetaljer på länknivå har genomförts och simulerats för uplink-kontrollkanaler baserade på vår resursallokeringslösning.