Effectively solving the Nurse Rostering Problem enhances nurse moral and leads to improved patient care. While the use of ejection chains has shown promise in previous studies, studying their impact on real-life instances from two Dutch hospitals further deepens our understanding of their practical utility. This thesis begins by discussing the Nurse Rostering Problem (NRP) as presented in literature, highlighting the lack of research conducted in real-life settings. We then describe the context of Dutch hospitals by defining the relevant hard and soft constraints. Afterwards, a review of previous NRP solutions is provided, covering various solvers and techniques, including ejection chains. Ejection chains are an approach that combines multiple local search moves into a larger one, where each move forces (ejects) the next move. These moves are executed consecutively, forming a chain. Two recent ejection chain approaches were identified for further investigation, and a novel approach is also proposed.

Afterwards, the concept of the three ejection chains is explained. The first ejection chain, InfeasibleEC, is inspired by Kingston, and explores regions of the search space that contain infeasible rosters. It starts with a swap that introduces a single hard constraint violation, but results in lower roster penalty. Then the ejection chain proceeds with a series of repairs, where each repair fixes the previous violation, but may introduce a single new violation. Four different approaches to explore the search space were implemented. The second ejection chain described is EmulateEC by Curtois et al. This chain emulates human schedule planners by performing a series of vertical swaps. Each swap improves the penalty for one nurse but simultaneously increases the penalty for a different nurse. Thus, the next swap aims to improve the nurse whose penalty was worsened in the previous step. This series of swaps is repeated until a better roster is found. The third ejection chain, RuinRecreateEC, repeatedly performs ruin and recreate operations in sequence. The idea is that each ruin and recreate operation makes a relatively small change to the roster, and by repeating the process multiple times, the final roster undergoes substantial diversification while still retaining much of the structure of the original roster.

All three ejection chains underwent individual parameter tuning using a sequential greedy tuning strategy to identify suitable parameter configurations based on two instances from the same hospital. Once tuned, the chains were further tested by rerunning the chains on the initial instances as well as on additional instances from a second hospital to assess their robustness. We analysed the breakdown of the penalty based on the different soft constraints, and investigated the impact of the chains on finding better rosters throughout the running time. We could not find improvements on specific soft constraints penalties, nor on finding better rosters faster. A significance test was conducted to determine whether the chains significantly reduce the penalty of the final rosters. There was insufficient evidence to conclude a statistically significant improvement.

This work proposes a pseudo-Boolean optimisation model that computes the minimum number of edge deletions needed to fully anonymise a graph, according to the (n,m)-k-anonymity measure. We survey the usability of this model, by comparing it with an unpublished Integer Linear Program (ILP) optimisation model in terms of running time and memory consumption. For both models, we provide a comparison between two different model solvers. We find a noticeable difference in running time and quality of the solution of the different model solvers. The experiments suggest that both running time and memory consumption of solving the pseudo-boolean model are greater than solving the ILP model by a constant factor. This opens up the possibility for the model to be used in tandem with a pseudo-Boolean proof verifier to provide certificates of solution optimality.

Network anonymisation is an essential procedure in processing data structured as graphs to achieve non-identifiability of participating entities. This quality is particularly desirable among networks representing stakeholders whose identity should not be compromised for ethical or legal reasons or when such structures are publicly disclosed. Extensive use of sensitive graph-like data contributed to the development of anonymisation methods that vary in terms of performance given the network topology or imposed constraints. We present modifications to an existing greedy algorithm using equivalence classes and discuss the rationale behind them. The experimental results obtained on networks from various scientific fields indicate that algorithms taking into account the size of equivalence classes in edge evaluation can consistently outperform the existing greedy algorithm in terms of the solution quality for larger number of available deletions. The proposed improvements also lead to comparable running time.

An increasing volume of data is being collected for research purposes, often containing sensitive information. Leaving out unique identifiers is insufficient to ensure anonymity. One approach to mitigating this risk is to modify the graph structure by adding or deleting edges. Existing heuristic approaches offer speed but limited optimality, while exact methods can achieve better anonymization quality but are computationally expensive. This creates a need for strategies that balance solution quality and efficiency. We propose a method based on simulated annealing that removes edges from the original network structure to achieve
anonymization under two formal privacy models: (n, m)-flavoured k-anonymity, which considers a node’s degree and number of incident triangles, and d-k-anonymity, which is based on the structure up to depth d of a node. Our method aims to balance running time and solution quality while adhering to an edge deletion budget. Experimental results on several real-world social network datasets show that Simulated Annealing can outperform traditional methods in terms of anonymity quality, particularly when higher modification budgets are
allowed. The running time is comparable to that of the baseline methods for smaller and medium-sized graphs but higher for larger graphs.

In the age of the internet, social networks are being used to study different phenomena, such as segre- gation, disease spread, or even peer influence. This introduces the need to protect the privacy of the in- dividuals that are part of these networks, a problem known in the field of network science by the name of network anonymization. This involves altering the initial network using different methods such as adding, removing, or altering edges, in order to pre- vent attackers from identifying specific individuals. One aspect that has been studied is the data util- ity of the anonymized network: if we alter the ini- tial network too much, its usability for studies is lowered. Thus, in this work, we propose a con- straint programming approach that minimizes the anonymization cost, in turn maximizing the data utility of the final network. We introduce a new iso- morphic_neighborhoods constraint and show that, for small(n < 20) or highly dense graphs, we can guarantee the maximum data utility, by adding the fewest number of edges that guarantee anonymity.

In network science, user privacy is a major concern when handling data such as social networks. These often contain sensitive data on \eg, individuals, companies, and governments. Therefore, it is essential to adequately anonymize this data before sharing or publishing to protect privacy and encourage open science. In this thesis we address this problem by studying k-anonymity in social networks. Specifically, we focus on (n,m)-k-anonymity measure. Building on an existing Integer Linear Program (ILP) encoding that achieves anonymity through edge deletion. We modify this encoding to add edges as well. Additionally, we propose a heuristic to improve the running time and memory usage of the modified ILP. We compare the anonymization settings, adding and deleting edges, on synthetic and real social network datasets, evaluating their running time, memory usage, and solution quality. This analysis provides insights into the trade-off between the two settings.

Grocery delivery company Picnic has identified affordable meal planning, especially in the context of recipe-based shopping, as an ongoing challenge faced by its customers. While recipes enhance customer experience and operational efficiency, Picnic currently lacks an algorithmic system to recommend recipes in a cost-effective way. This research addresses this gap by proposing a scalable optimization approach that minimizes the total cost of grocery products across a set of selected and recommended recipes.

To address this challenge, the paper formulates the problem as a Mixed Integer Linear Program (MILP), chosen for its ability to guarantee a globally optimal solution. The MILP model selects a combination of recipes and corresponding products that promote ingredient reuse and bulk purchasing to minimize overall cost. To complement this, the study implements two meta-heuristic models: a standalone Genetic Algorithm (GA) and a hybrid GA+MILP model, where GA selects recipes and MILP optimally assigns products. The optimization process also incorporates real-world constraints such as minimizing food waste and ensuring cuisine consistency.

Experimental results show that the MILP formulation consistently achieves substantial cost savings compared to a naive baseline, which selects the same set of recipes but does not optimize product choices across them. Gurobi outperforms CPLEX in solve time while maintaining identical solution quality. The standalone GA yields near-optimal solutions in seconds, while the hybrid GA+MILP model improves accuracy further, albeit with increased computational cost. When constraints such as waste reduction are added, the system remains effective, with one multi-objective variant reducing waste at minimal cost increase.

The findings confirm that cost-aware recipe recommendation is feasible, efficient, and adaptable. The proposed system offers a foundation for future extensions toward sustainability, personalization, and real-world deployment at Picnic.

Model Counting solvers are critical in many domains. One way of validating them is through fuzzing. However, current fuzzing approaches lack systematic methods to evaluate how different test generators compare in bug-triggering behavior. This paper proposes three methods for evaluating fuzzer similarity: black-box analysis, differential testing, and white-box analysis.

A similarity metric was defined using differential testing, incorporating solver behavior, solve time, and count differences. A case study was conducted on three fuzzers across numerous configurations and four SOTA model counters, followed by an analysis of correlations between CNF feature distribution similarities and fuzzer behavioral similarities.

The results show moderate correlations between graph structure features (minimum variable node degrees) and fuzzer similarity, while clause balance features show negative correlations. However, the method proves inconclusive for selecting dissimilar fuzzers due to limited incorrect counts in our dataset, uncertainty about crash causes, and the similarity metric's inherent subjectivity. Further research is needed, either by expanding the scope of the experiment with more diverse fuzzers, CNF features, and counters, or by pursuing another method recommended by this study.

Model counting (#SAT) is a fundamental problem in theoretical computer science with applications in probabilistic reasoning, reliability analysis, and verification tasks. Despite advancements in solvers and #SAT instance generation, existing benchmarks fail to fully capture the diversity of structural features that influence solver performance. This paper introduces a feature-driven #SAT instance generator that systematically varies the fraction of Horn clauses across the full range (0% to 100%), enabling a rigorous evaluation of solver performance. Results reveal a “U-shaped” correlation between solve times and Horn-clause fractions and a strong relationship with model counts, exposing computational bottlenecks. Our contributions include the generator design, experimental validation across multiple solvers, and insights into improving solvers for challenging structural configurations, advancing #SAT research.

Weighted model counting (WMC) solvers play a key role in Bayesian inference applications, used for medical diagnosis [17] [16] and risk assessment [14]. Ongoing efforts to improve WMC solver developers aim to develop a fuzzer to identify bugs. This research is aimed at enhancing the quality of this fuzzer by developing an additional method to generate WMC instances, EXTREMEgen [21]. The functionality of this new approach relies on generating practical instances from Bayesian networks and breaking the solvers using extreme weights. Our empirical experiments show that EXTREMEgen exposes bugs in state-ofthe-art WMC solvers. The generated instances are solved fast enough to be usable in fuzzing. However, generation speed needs to be optimized to become practical for fuzzing. When optimized, EXTREMEgen could become the first generator of WMC instances specifically designed for fuzzing.

Propositional model counting (#SAT) is the counting variant of the Boolean Satisfiability (SAT) problem. Development of #SAT solvers has seen a boom in recent years. These tools are complex and hard to debug. To address this, we propose a delta debugger that reduces fault-triggering unweighted model counting instances. Our delta debugger shows an improvement compared to state of the art in the related field of SAT solvers.