This thesis gives an overview of the Shannon Switching Game, Lehman’s necessary and sufficient conditions for the game to be short, cut or neutral and the corresponding strategies, and an...Show moreThis thesis gives an overview of the Shannon Switching Game, Lehman’s necessary and sufficient conditions for the game to be short, cut or neutral and the corresponding strategies, and an elaboration of Bruno and Weinberg’s application of Kishi and Kajitani’s results to finding a pair of disjoint cospanning trees in a graph if the game is short. The main contributions of this thesis are providing Lehman’s results and their proofs with graphical examples to make them easier to read, and the elaboration of Bruno and Weinberg’s algorithm mentioned above.Show less
In Computed Tomography, it is often standard to scan an object with the projection angles spread equidistantly over the full rotation of the object. If the number of projection angles is relatively...Show moreIn Computed Tomography, it is often standard to scan an object with the projection angles spread equidistantly over the full rotation of the object. If the number of projection angles is relatively small (e.g. because of radiation damage), the choice of the distribution of these angles is important. Especially if the object has certain main directions, in which the most important features are aligned, the reconstruction can be improved by selecting angles in these directions. In this thesis, possibilities for improving the choice of projection angles are investigated. Three angle selection algorithms are discussed: a greedy algorithm, a coordinate descent algorithm and an adaptation of the ensemble Kalman Filter algorithm. The algorithms try to find the minimum of a cost function, which is based on the L 2 -norm. The performance of these algorithms is shown on three computer generated phantoms and one real-world image, generated from scanning a wooden tree stem in the FleX-Ray scanner at CWI. The results of choosing angles with the algorithms are compared with choosing equidistant projection angles. The results show that especially the coordinate descent method is capable of finding projection angles that lower the cost function. In real life situations the true image is not available. Therefore, the possibility of using training data to estimate the cost function in that case, is investigated. We assume that these training samples come from the same probability distribution as the true image. Then, averaging over the cost function of these training samples improves the choice of projection angles with respect to equidistantly chosen angles.Show less
In this thesis, we will consider two versions of a discount single server system with exponentially distributed arrivals and departures on a discrete time scale. In the first model, to be discussed...Show moreIn this thesis, we will consider two versions of a discount single server system with exponentially distributed arrivals and departures on a discrete time scale. In the first model, to be discussed in Chapter 1, we add a reward for every customer who has been served, and a fee for each time step a customer is in service. We also add arrival control. The model is described in more detail in Section 1.1. The goal is to find an optimal strategy that minimizes the expected total discounted cost (Section 1.2). To find this strategy, we use a direct, explicit algorithm called value iteration. This strategy turns out to be a threshold strategy: a given amount of customers is allowed to enter the system, and once this amount of customers is present, any newly arriving customer is refused. Furthermore, we prove monotonicity properties of the model in Section 1.3. Lastly, the n-horizon cost function of value iteration is decomposed into a subsequent application of different operators (Section 1.4). In the second chapter, the model of Chapter 1 is used, with the addition of departure control. We add an extra, faster server, so we have a slower Server 1 and a faster Server 2, and we can choose at any transition moment which server to use. Using Server 2 involves extra costs per time unit. A detailed description of the model can be found in Section 2.1. In this model, we again want to find an optimal policy (Section 2.3), but now we first rewrite the explicit algorithm as a consecutive application of operators (Section 2.2). It turns out that we can split these operators into operators deciding whether or not an incoming customer should be accepted, and operators deciding which server to use. This was a surprising result, as we did not know in advance that the two decisions can be made independently from each other. Using these operators, we find that the optimal policy is a two-dimensional threshold strategy. In Section 2.4, we give a theorem on the relationship between the two thresholds. Furthermore, we prove the convergence of the thresholds, and thus the strategy, and of the nhorizon relative cost function, by using two initial functions such that one approaches the optimal value function from below and the other from above (Section 2.5). This shows that the choice of the starting functions affects the results, which was unknown so far. Finally, we prove that such functions exist and give a numeric example to demonstrate the results graphically (Section 2.6).Show less
To determine an optimal strategy for a multi-class server, with impatient customers, can be difficult. There are heuristics, such as the Whittle index, that perform well under restrictive...Show moreTo determine an optimal strategy for a multi-class server, with impatient customers, can be difficult. There are heuristics, such as the Whittle index, that perform well under restrictive conditions. We discuss a few of these heuristics and their merits and drawbacks. To overcome these drawbacks, we experiment with a data-based approach, by generating data using value iteration and predicting a strategy with a neural network. Furthermore, we explore the effect of different parameters on the performance of the neural network, for a particular case. Moreover, we look into more extensive methods such as combining the prediction of multiple neural networks and using neural networks to choose the training data.Show less
In his thesis, we will first outline the theory of stochastic cooperative game theory without transfer payments, as developed by Borm, Tijs and Timmer in [6]. We will compare and contrast it with...Show moreIn his thesis, we will first outline the theory of stochastic cooperative game theory without transfer payments, as developed by Borm, Tijs and Timmer in [6]. We will compare and contrast it with classical cooperative game theory. Subsequently, we will use this theory to model a two-player game in which owners of intermittent renewable energy sources (such as wind mills and solar panels) could cooperate in order to minimize their fine due to prediction errors of their production. We will describe two different kinds of cooperation and compare and contrast them in terms of their respective beneficiality to the players involved by computing the core. Furthermore, we will consider the case in which the prediction errors of the players are correlated. Subsequently, we compute the Shapley values of the two-player game, after which we generalize our results to the case of three participating players. Throughout this thesis, we stress the practical relevance of this work to real-world examples by pointing towards and incorporating previous experimental work on the actual prediction error distributions of renewable energy production devices.Show less
Many practical optimisation problems can be formulated as a traffic assignment problem, i.e. optimally route a multi-commodity flow through a network. In order to do this, a network is defined that...Show moreMany practical optimisation problems can be formulated as a traffic assignment problem, i.e. optimally route a multi-commodity flow through a network. In order to do this, a network is defined that can capture congestion and a notion of optimal flow. The shortest path problem is derived as a sub-problem of the traffic assignment problem, discussing several algorithms that can solve it. In addition, several speed-up techniques for the shortest path problem are described that can be applied to static networks. In conclusion, an algorithm is discussed that solves the traffic assignment problem by iteratively solving a shortest path problem.Show less
The High School Scheduling Problem is the operational research problem of finding an optimal timetable for students and teachers in a secondary school. It is a minimisation problem, in which we...Show moreThe High School Scheduling Problem is the operational research problem of finding an optimal timetable for students and teachers in a secondary school. It is a minimisation problem, in which we need to satisfy as many wishes as possible while guaranteeing all demands are satisfied. The High School Scheduling Problem has been studied for over half a century, owing to the importance of schools having a good schedule and the difficulty of finding a schedule that adequately satisfies the different constraints. This thesis studies two new approaches to optimising solutions of a problem instance. Both of these approaches are based on transformations of the problem’s search space. First, locally optimal solutions are improved by changing the penalty associated with soft constraints in specific ways. Secondly, the schedule’s penalty function itself is improved, aimed at shifting focus from improving the schedule as a whole to making sure individual schedules become acceptable.Show less
The Game of Cops and Robbers is played by two players on a graph, the one player controlling a set of cops and the other controlling a robber. The goal of the cops is to capture the robber in a...Show moreThe Game of Cops and Robbers is played by two players on a graph, the one player controlling a set of cops and the other controlling a robber. The goal of the cops is to capture the robber in a finite number of moves, whereas the robber wants to evade the cops indefinitely. The central question we ask is: how many cops are needed on a given graph for them to be able to win the game? This amount is called the cop number of a graph. In this thesis, we give an extensive overview of results that give an upper bound on the cop number for graphs of a given type, like unit disk graphs and string graphs, as well as some examples of these graphs having a high cop number. In this overview, we will see that the results all greatly depend on the statement or proof method of one of two theorems published by Aigner and Fromme [1]. In addition to a survey of the existing work, we explore whether the two main theorems can be used to further sharpen these results. Leading to mostly negative answers, we conjecture that a different approach is necessary in order to book further progress.Show less
The supply chain network of companies that produce goods and deliver them to customers, can be captured in a mathematical model. ORTEC Supply Chain Design (OSCD) uses a mixed integer mathematical...Show moreThe supply chain network of companies that produce goods and deliver them to customers, can be captured in a mathematical model. ORTEC Supply Chain Design (OSCD) uses a mixed integer mathematical program to design a supply chain network while optimizing a certain output (e.g. minimize cost). The input parameters of such a program, like transport cost and customer demand, not only have to be estimated, but they also have ranges of uncertainty. Consequently, the output (the network design) is uncertain as well. In this work the impact of that uncertainty on the output, in the mathematical model of OSCD, is investigated. Generic effects that hold for several case studies of OSCD are presented. In addition a tool for precise estimation in unique cases is proposed. This work could be used to further extend the relationship between input and output of more complex case studies of OSCD.Show less
A formalization for the Paradigm coordination language is introduced, in terms of graph products and Markov processes. The n-arm robot problem is presented, where a robot composed of several...Show moreA formalization for the Paradigm coordination language is introduced, in terms of graph products and Markov processes. The n-arm robot problem is presented, where a robot composed of several jointed arms tries to plan and to move. We find that the n-arm robot problem reduces to a concurrent competition for the space in which the arms evolve. This competition for space reduces to the classical reader/writers problem. Moving in space is equivalent to writing and sensing in space is equivalent to reading. Several coordination schemes for the arms are developed in Paradigm. Multiple arms can plan paths concurrently, but reserving space to move has to be done sequentially, and moving can be done concurrently. The solutions are simulated in Matlab, and the code is provided. Thereupon, the solutions are compared, and it is shown that not all coordination schemes are equivalent. Finally an outline of future work is provided.Show less