The increasing integration of Renewable Energy Sources (RES), rising global electricity demand, and ongoing developments in power market structures collectively increase the complexity of Energy Management Systems (EMS). The tight scheduling of interdependent decisions in a Rolling Horizon (RH) Mixed Integer Linear Programming (MILP) environment requires efficient formulations to remain scalable and flexible to future innovations. This thesis investigates initialization strategies (warm starts) that leverage previous optimal system configurations to reduce computational complexity and solution time. Iterative cycles of variable selection, warm start execution, and problem reformulation are evaluated across multiple scenarios. These scenarios vary in modeling horizon, day-ahead price profiles, market engagement strategies, and environmental and system conditions. Problem reformulations include adjustments in the treatment of violation decision variables, linear reformulations, and the use of Benders decomposition. The results demonstrate that successful warm start implementations can substantially reduce solution times and provide valuable insights for further tightening problem formulations. Overall, the study provides guidance on efficient formulations that support effective initialization and enhance solver performance across a wide range of users and system configurations, thereby contributing to more scalable and widely applicable energy optimization practices. Keywords: Rolling Horizon (RH), Warm Start, Unit Commitment (UC), Mixed Integer Linear Programming (MILP), Benders Decomposition

Stemmatology is the study and reconstruction of textual genealogy and has several similarities to phylogenetics, the study of evolutionary histories of species. Current methods in computational stemmatology often borrow tools from phylogenetics, yet classical phylogenetic models are not well suited to the structural and labelling requirements of manuscript traditions. In particular, phylogenetics typically assumes leaf-labelled trees or networks and lacks the means to accommodate internal labels—a feature which is crucial in stemmatology. Nonetheless, these models are frequently used as there are few formal alternatives.

This thesis addresses that gap by studying the encoding and reconstruction of internally labelled trees and networks from rooted triplets. Specifically, we consider three classes of graphs: multifurcating rooted trees, general rooted trees (allowing nodes with out-degree one), and level-1 networks. Each graph is assumed to have labels on a subset of its vertices, including all leaves and some internal nodes. We prove that, under limited assumptions, a complete set of rooted triplets uniquely determines the structure and labelling of each of these graph classes up to isomorphism. This generalises earlier results for leaf-labelled binary trees and extends triplet-based encoding to structures with internal labelling and limited reticulation.

Building on these encoding theorems, we develop polynomial-time algorithms to reconstruct each graph class from its full triplet set. For trees, our methods generalise previously proposed algorithms by allowing multifurcations, nodes with out-degree one, and labels at internal vertices. For level-1 networks, we design a reconstruction algorithm that correctly identifies cycle structures and label placement, adapting earlier techniques for dense triplet sets. All reconstruction algorithms are proven correct and theoretically efficient under the given assumptions. The algorithms have been tested on many instances and run quickly.

To compare internally labelled graphs, we introduce an extension of the classical triplet distance. This adapted metric counts differences in triplet sets between two graphs on the same label set. We evaluate the metric and reconstruction algorithms on synthetic and real-world data, demonstrating their ability to capture meaningful structural differences and to recover known graphs from complete or near-complete triplet information. These results show that rooted triplets form a robust foundation for reasoning about internally labelled structures in both tree-like and mildly reticulate settings. The theory and algorithms presented in this thesis provide new tools for computational phylogenetics and stemmatology, enabling the reconstruction and comparison of complex transmission histories from local relational constraints.

Link to the GitHub page containing all the code - https://github.com/TMALevert/LAOML

We introduce two novel optimization problems on vertex-weighted multilayer graphs: the Predecessor Dense Reachable Subgraph (PDRS) problem and the Neighborhood Dense Reachable Subgraph (NDRS) problem. In PDRS, the aim is to find a subset of vertices that maximizes the ratio of the total vertex weight to the size of its predecessor neighborhood, under reachability constraints. A subset is considered reachable when it is a union of paths from the first layer to the last. The NDRS variant is equivalent to the PDRS problem, but the size of the entire neighborhood is used for the denominator of the objective function. The motivation for these problems comes from money laundering detection. We prove NP-hardness by reduction from the Vertex Cover problem and formulate MILPs that give exact solutions to the problems. Additionally, we show that the single path variant, where the solution space is restricted to single paths from the first layer to the last, can be solved in polynomial time using dynamic programming. We introduce a heuristic algorithm called Greedy Single Paths, which starts with the empty graph and uses an exact algorithm for the single path variant to iteratively grow the solution. We also introduce a heuristic algorithm called Greedy Peeling. This algorithm starts with the whole graph and iteratively peels vertices from the allowed neighbor set. The algorithms are implemented and tested on synthetic data sets to assess their performance in terms of running time and solution quality.

Evolution can be modelled by semi-directed phylogenetic networks, partially directed graphs where directed edges represent reticulate evolutionary events. In this thesis, we present a polynomial-time algorithm that can reconstruct a level-2 semi-directed phylogenetic network from its quarnets (4-leaf subnetworks). First, we find a canonical form of a network by reducing our information to merely quarnet-splits. Here, we use the blob-tree of the network found with quarnet-splits to construct the canonical form of the network. Finally, we consider quartets, which give more information about level-1 and level-2 quarnets, to refine on the canonical form.

Phylogenetics is the study of how species are related through evolution. These relationships are traditionally represented using branching diagrams called phylogenetic trees. However, certain evolutionary processes, such as hybridization or horizontal gene transfer, cannot be represented by trees alone. Therefore, phylogenetic networks - which allow additional connections between branches - are used to capture more complex evolutionary histories.
As phylogenetic networks become more complex, it becomes harder to determine whether a particular network can be uniquely reconstructed from observed DNA sequence data. This leads to the concept of identifiability. A network is said to be identifiable if, in theory, it can be uniquely determined from the data it generates. If two different networks produce the same data under a given evolutionary model, they are not identifiable from that data. Identifiability is essential for developing reconstruction methods that aim to infer evolutionary relationships from DNA.
This thesis investigates a specific class of phylogenetic networks, known as trinets. A trinet is a small sub-network that describes the evolutionary relationship between just three species. Trinets are useful building blocks for understanding and reconstructing larger phylogenetic networks. The main question studied in this work is whether these trinets are identifiable. We investigate whether specific types of trinets can be distinguished from simpler tree structures, using a mathematical approach based on phylogenetic invariants. These are special algebraic expressions that relate to the probabilities of observing certain DNA patterns. By evaluating such invariants, we may be able to detect whether the data came from a network or from a tree.
This thesis provides new insights into the identifiability of trinets. It shows that a specific type of trinet can be distinguished from a simple tree using an invariant. This is an important step toward understanding how more complex evolutionary networks can be identified from biological data from genes.

This thesis explores the integration of machine learning (ML) into algorithm design for solving complex combinatorial optimization problems. We focus on solving problems that arise in bilevel optimization, two-stage robust optimization, and phylogenetics. Although these problem classes seem vastly different, they share the common characteristic of being extremely challenging to solve. Current solution methods for these problems are computationally heavy and their solving duration is often impractical for already small-sized instances. Adding a component of machine learning also adds complexity. We primarily attempt to mitigate this effect by proposing learning methods that utilize efficient training data generation schemes that rely on solving sub-problems or are even based on a simple procedure, instead of learning from optimal solutions of many instances similar to the target problem.

This thesis addresses a timetabling problem known as Strategic Passenger-Oriented Timetabling (SPOT). SPOT is a timetabling problem that involves assigning departure and arrival times to train services. Unlike classical timetabling, which typically emphasizes infrastructural feasibility, SPOT shifts the focus toward enhancing the passenger experience without infrastructural constraints. The timetables generated by SPOT provide information regarding important connections for passengers and can later be adjusted to accommodate infrastructural constraints. SPOT evaluates a timetable based on the perceived travel time consisting of drive, dwell and transfer times, along with additional penalties for inconveniences by transfers and initial waiting times of passengers.

An initial research focused on using a Mixed-Integer Linear Programming (MILP) approach to solve the SPOT problem. However, this MILP formulation has multiple problems. The MILP tends to perform slow for small problem instances and becomes significantly worse as the problem size increases. Additionally, the effectiveness of the timetables generated by the MILP are often unreliable, because there is a substantial gap between the perceived travel time of the best-found timetable and the best-found lower bound.

This thesis explores a heuristic approach to solving SPOT. Specifically, two heuristics are employed: Local Search and Simulated Annealing. Both operate by exploring a neighborhood of possible timetables around a current timetable to identify better alternatives. The absence of infrastructural constraints in SPOT simplifies the creation of these neighborhoods, as different train services do not influence each other. Additionally, multiple lower bounds are calculated for the perceived travel time, providing benchmarks to evaluate the quality of the solutions. Overall, these heuristics are effective in finding good timetables within a short period, with the lower bounds being reasonably close to the perceived travel time of the generated timetables.

In the study of phylogenetic trees and -networks, it is frequently desirable to have a measure
of the distance between them. A potentially useful definition of this distance is the length (in
steps) of the shortest path from one to the other, where this path consists of single rearrangement moves of certain types. While there have recently been developments in methods for finding the shortest path between ranked phylogenetic trees, we will instead be inspecting paths between ranked phylogenetic networks in this work. The primary difference between trees and networks here is in the presence of reticulations in the latter, which are moments where different "branches" come together. More specifically, we work out an algorithm that will provide a path between any two binary, level-1, phylogenetic networks with some restrictions, so as to lay the groundwork for work to find shortest paths within this space

The security of sensitive areas against adversarial threats is a critical concern, necessitating the development of effective patrol strategies. This thesis addresses the problem of optimal patrolling in adver- sarial scenarios through the formulation of an analytical method to calculate the interception probability of a possible attacker in a graph-based patrolling game. By leveraging Markovian strategies, the research provides a robust framework for efficiently calculating interception probabilities and proposes a methodology to optimize patrol routes.

Firstly, the structure and modeling framework that is used in this thesis is set out. Subsequently, a probabilistic, a recursive, and a matrix-product method are derived to calculate the interception probability. This constitutes the core of this thesis. Lastly, the discussion is extended by applying the matrix-product method to practical examples. Monte Carlo simulations are used to compare the performance of different patrol strategies under varying conditions. The results illustrate how the developed methods enable detailed performance analyses, showing that the effectiveness of patrol strategies can vary based on the distribution of attack strategies.

Key findings highlight the impact of graph structure and attack strategy distributions on interception probabilities, the scalability and practicality of the matrix product method to calculate the interception probability, and the significant computational efficiency gained by using this approach. The research also outlines several avenues for future work, including the exploration of heterogeneous environments, optimization improvements, and multi-agent scenarios. Overall, this thesis contributes to the field of patrolling games by offering enhanced methods to evaluate and optimize Markovian patrol strategies, providing both theoretical methodologies and practical implementations that can be used to improve security in adversarial settings.

In the study of evolutionary biology, there exists a method called the “cherry picking algorithm” that produces the instructions needed to create a network that shows how different species are related.
This report explores what happens when the algorithm starts with a wrong choice, or a “suboptimal cherry” for the first step of the algorithm, and how this affects the accuracy of the algorithm. Imagine you are trying to build a family tree for different species, but you start with a mistake. This research looks at how such initial mistakes can impact the accuracy of the entire family tree. We conducted this study
using simulations of the algorithm that deliberately make an initial mistake, and afterwards continue as the algorithm would normally. The study found that starting with a wrong step in the algorithm usually makes the performance of the algorithm worse. Specifically, it lead to an average optimal performance decrease of 34,8% for networks relating a smaller number of species, and 11.3% for networks relating a larger number of species. Interestingly, the larger the number of species we are attempting to relate in the network produced by our algorithm, the less severe the impact of the initial mistake.
We concluded that making an initial mistake negatively effects the average performance of the algorithm, and the extent of the effect varies with the number of species we are trying to relate in our network.

Reconstructing a minimum reticulation network from phylogenetic trees is used in evolutionary studies. In this thesis, we focus on finding temporal networks using cherry-picking sequences for binary trees with all taxa. Finding such a minimum reticulation temporal network is NP-hard.

We introduce an algorithm to find a minimum reticulation network with a running time of O(2^n poly(n,t)). In addition, this study explores potential enhancements to the algorithm through the utilisation of branch and bound.

Additionally, we introduce a similar algorithm to determine the existence of a temporal phylogenetic network. This algorithm is improved upon by integrating a new concept called cherry growing. This leads to a notable speed-up in performance.

Furthermore, we examine the application of Graph Neural Networks (GNN) in heuristics to find a cherry-picking sequence which can be used to construct a network. This is done by classifying leaves into good, which leads to optimal solutions, and bad leaves. To assess this, two types of data were employed: one simulating evolutionary models and the other employing a fully random approach. The best-performing GNN model has a 97.4% accuracy for evolution-based data and a 79.1% accuracy for random-based data.

The GNN models are implemented as predictors in two classes of heuristics. The first generates a cherry-picking sequence by repeatedly picking leaves. The second class of heuristics is based on a tree search heuristic. This tree-search-based heuristic outperforms the cherry-picking-based heuristic. Furthermore, the GNN heuristics outperform their random variant, even for problems substantially larger than the GNN was trained on.

We also examine the use of GNN in predicting the existence of a phylogenetic temporal network given a set of trees. The best-performing GNN found for this problem has an accuracy of 80.3%.

Phylogenetic trees are commonly utilised in evolutionary biology. These trees represent the evolution of a set of species. In case of gene transfer however, a phylogenetic tree is insufficient. In such cases, tree-based phylogenetic networks are more suitable as they can depict reticulate evolution.
Nonetheless, tree-based phylogenetic networks have their limitations as they are unable to represent reticulate events occurring between different environments, families, or lineages of species. To address this, forest-based networks offer a solution.
A forest-based network is a collection of leaf-disjoint phylogenetic trees with arcs added between different trees in case of reticulate evolution.
In this thesis, an integer linear programme (ILP) is created to determine whether a binary phylogenetic network is forest-based. It is important to note that this thesis exclusively focuses on binary phylogenetic networks.
This ILP model is expected to be valuable in the development of new models and algorithms for both binary and non-binary phylogenetic networks, thereby enhancing the understanding of reticulate evolution. Additionally, the ILP may lead to time-related challenges when processing bigger phylogenetic networks.

Phylogenetic networks are a specific type of directed acyclic graph (DAG), used to depict evolutionary relationships among, for example, species or other groups of organisms. To solve computationally hard problems, treewidth has been used to parametrize algorithms in phylogenetics. In the hope of simplifying the algorithmic design process, Berry, Scornavacca and Weller recently proposed a new measure of tree-likeness that takes into account the directions of the arcs: scanwidth. They showed that the corresponding decision problem of this parameter - which can be seen as a variant of directed cutwidth, using a tree instead of a linear ordering - is NP-complete. This thesis aims to widen the structural knowledge of scanwidth and to find efficient ways of computing it on general DAGs, both by exact and heuristic algorithms.

With the help of reduction rules, we construct an explicit dynamic programming algorithm that computes scanwidth exactly, along with its corresponding tree extension, in O(k * n^k * m) time for rooted DAGs of scanwidth k. This slicewise polynomial algorithm proves that computing the scanwidth is in the complexity class XP. The algorithm also functions as an FPT algorithm for networks of level-l, with the complexity bounded by O(2^4l-1* l * n + n²). It performs well in practice, being able to compute the scanwidth of networks up to 30 reticulations and 100 leaves within 500 seconds.

On the heuristic side, an algorithm that repeatedly splits at a specific type of smallest cut is proposed. Enhanced with simulated annealing, this heuristic shows promising results, obtaining an average approximation ratio of 1.5 for large synthetic networks of 30 reticulations and 100 leaves. Applied to a real-world dataset of networks, the heuristic performs near-optimal. Although we prove that the scanwidth is always greater than or equal to the treewidth, experiments show that they are close to each other in practice. This further motivates the use of scanwidth over treewidth as a parameter in algorithms.

In biology, phylogenetics is the study of the evolutionary history of and relations between e.g. species. Such data are often represented in trees. Remarkably, trees lack the representation of reticulation events, such as hybridization, while such events are believed to be important. One of the reasons why trees are widely used, is the enormous complexity of inferring a network directly from DNA data.
Therefore, indirect approaches are studied. One option is to construct a network from trees, which have been constructed from DNA data. Another option, which is studied in this work, is to create a network which represents all clusters from the trees. We are interested in finding a network having the lowest level possible, i.e. the lowest number of reticulations per biconnected component. The Cass algorithm is one of the best algorithms in this respect. However, it does not always give optimal results. In this thesis, an optimal algorithm is presented called STCass, of which many ideas are inspired from Cass. We lay
theoretical foundations on how to build an optimal network. Furthermore, (greedy) steps are proposed to solve the problem, which seem to work very well in practice. Based on several optimizations that are proposed, an improved algorithm called MSTCass is presented, which runs faster than STCass, in general. In order to speed up any Cass-based algorithm or derivatives of it, several lower bounds are presented on the reticulation number r(N) per biconnected component N of an optimal network. Besides, a new upper bound on r(N) is conjectured which can be evaluated in seconds, although e.g. an upper bound obtained by the HybridInterleave or PIRN algorithm is mostly lower and which can be evaluated often in twenty minutes for the tested instances.

TreeContainment is a well-known problem within phylogenetics, which asks whether a binary phylogenetic tree is embedded in a binary phylogenetic network. For this problem, Jones, Weller and van Iersel (2022) have created an algorithm that uses dynamic programming on tree-decompositions to achieve a running time that is exponential in the tree-width parameter instead of in the number of reticulations. However, due to the implicit formulations of two crucial steps in this algorithm, this running time cannot be achieved in practice without finding ways to generate the required structures explicitly. This paper provides two new sub-algorithms that can do that. To further improve the performance of the algorithm, I introduce a number of criteria and other methods that can be used to reduce the number of structures generated. Additionally, I describe a way to manipulate the nice tree-decompositions to create a more favorable order of bags for the dynamic programming. These sub-algorithms and improvements are used by two new algorithms TWITCH and PITCH, whose implementations are compared to a brute force algorithm and a new branching cherry-picking algorithm named BOTCH. The latter has an FPT running time that is exponential in the number of vertices that have only reticulations as children. The comparisons show that the implementations of the dynamic programming algorithms TWITCH and PITCH are slower in practice than the brute force algorithm, despite their numerous improvements. Of the four new implementations, BOTCH has the best test results and it is shown to be fast in practice.

The problem considered in this thesis is the box set optimization problem. In
this problem the goal is to find the optimal dimensions of a number of shipping
boxes which have to provide an optimal fit on a set of items. The application
considered is e-commerce, and hence the number of items is relatively large
compared to other applications found in literature.

The literature describes multiple problem formulations where a small num-
ber of optimal shipping boxes are selected from a large set containing candidate
boxes. However, since the instances considered in e-commerce application are
often too large to be solved in this way, we introduce a simulated annealing
heuristic solution method. In this way we are able to generate box sets con-
taining 10 to 20 boxes with centimeter accuracy for data sets containing up to
XX single item orders.

We pay special attention to an algorithm to very efficiently calculate the
objective value associated to the fit of a selection of candidate boxes on a set of
items. This is done by assigning items to shipping boxes using a pre-calculation
table. Because the heuristic can process a larger set of candidate boxes than
the exact solution method, ultimately results of the heuristic are better than
those found by the exact solution method.

Finally we generate multiple box sets based on the input data provided by
the industry partner bol.com, and compare the results. We conclude that on
almost all tested instances, the total amount of carton used can be reduced by
more than XX in combination with a total send volume reduction of over XX
in comparison with the box set that is currently used. Furthermore, we answer
additional questions. We find that minimizing the total amount of carton used,
instead of minimizing the total volume send, can lead to a result that is most
desirable in practice. We discover that pack-line specific, warehouse specific or
seasonal specific box sets provide none to only minor additional improvements.

In this paper we give a historical and theoretical background to minimal triangulation and its relation to minimal separators.
We introduce a new type of minimal separators, the minimal meta separator, which its size is a lower bound for the treewidth problem, its fill-in is a lower bound for the minimum fill-in problem and can be used for the aid of enumeration of minimal separators.
Furthermore, we introduce the idea of transformation which are controlled graph modifications that predictably modify the minimal separators of such graph. Namely, we introduce the transformations of inclusion minimal clique decomposition, saturate minimal separator, edge addition and minimal meta separator decomposition. These transformations can aid the architecting of algorithms for the enumeration of minimal separators.
Finally, we then apply such methods on the problem of enumeration of minimal almost-clique separators and demonstrate faster runtimes compared to the current state of the art.

Phylogenetic networks generalize evolutionary trees and are commonly used to represent evolutionary relationships between species that undergo reticulate evolutionary processes such as hybridization, recombination and lateral gene transfer. In this thesis all quarnets, networks on four species, of a network are assumed to be known. We prove that each recoverable undirected or semi-directed binary level-2 phylogenetic network without redundant biconnected components is encoded by its set of quarnets, meaning that the network is uniquely determined by its quarnets. Furthermore, two decomposition theorems for undirected and semi-directed binary phylogenetic networks are presented. These decomposition theorems are proved for undirected binary phylogenetic networks for all levels and for semi-directed binary phylogenetic networks that are at most level-2.

Phylogenetic networks are used to represent evolutionary histories of a set of taxa. In this thesis, we look at a certain network class, called orchard networks.
In the beginning of this thesis, definitions concerning phylogenetic networks and specifically orchard networks are introduced. The characterization of orchard networks involves time-labelling of the vertices.
Then, an algorithm is given to see if a given network is orchard. The next section, explores a non-recursive labelling of a given network. There is not an explicit algorithm for the labelling. An algorithm for the labelling is given.
The last chapter is about non-orchard networks. It contains multiple actions that can be performed on the non-orchard networks in order to transform the non-orchard networks into orchard networks.

Describing phylogenetic trees or networks with a polynomial is a tool to distinguish between them. In this thesis, a new polynomial for describing rooted binary internally labeled phylogenetic networks and trees is introduced based on the research of P. Liu and J. Pons et al. Two different cases are considered, one where the reticulation nodes have distinct labels λ_i and one where the reticulation nodes have the same label λ. There are a few conjectures stated about the uniqueness of the polynomial and the relation of the polynomial with the primary subtrees and their monomial. Also the folding and unfolding of a network is described. Furthermore, an algorithm is provided with which a tree can be made out of different monomials. With use of the lemma that states when a tree can be folded to a network, it can be determined if the tree can be folded to a network.