Assignments (theses)

Researchers of DMMP work in several research areas with applications in different fields, like health care, traffic, energy, ICT, games and auctions, logistics and timetabling. The overview of previously completed theses gives an indication of what kind of topics for a final assignment are possible. We collaborate with different external partners outside of the UT for internships and final assignments, and to name only a few, that could be DAT.mobility, ORTEC, Thales, NS, CQM, and many more. Also foreign Universities are an option.  The list below in therefore indicative, and shows a few of the open problems to work on. If you are interested in assignments for an internship or master's thesis, please contact any member of the group.

List of ongoing and completed master theses.

The following list of potential MSc topics is always under construction and will be updated regularly. To get more information, you can always contact any of the staff.

Potential games for caching in 5G networks


Future mobile networks, 5G and beyond, will make use of proactive caching in the base stations. This means that based on predicted user behavior, content is placed in base stations before it is actually requested. The advantage is that delivery latencies are reduced, since once a request for content comes it does not need to be fetched from the server. Moreover, it enables load-balancing in the backhaul of the network, updating the content of the caches only if the network load is low. Since storage capacity in a base station is limited we cannot cache all content. At the same time, since most locations are covered by multiple base stations we want to prevent overlap in the cached content between those base stations. The mathematical challenge that arises is to decide which content to cache in which base station.

The resulting optimization problem is not convex and cannot be tackled straightforwardly. In this project you will work on a distributed optimization algorithm that can be interpreted as a potential game played between the base stations in the network. A basic version of such an algorithm has been proposed in the literature, but the underlying theory needs to be further developed. In this project you will develop this theory, with the purpose of providing performance guarantees on the algorithm (convergence rate, quality of solution,…) as well as refinements/improvements on the algorithm itself.

You will be working with algorithmic game theory and in particular with the class of (matroid) congestion games. In such a game we assume that the players behave selfish and are interested to optimize their personal utility only. Game theory predicts that such a behavior leads to an equilibrium solution which has been studied extensively. Interestingly, the distributed algorithm outlined above can be described as a game such that the solution of the algorithms corresponds to an equilibrium of the game. You will apply and refine game theoretic methods to analyze the quality of equilibria and the convergence rate.

Knowledge of 5G and/or caching is not required before starting this project.

Please contact Alexander Skopalik or Jasper Goseling.

Algorithms to Run Out Table Cooling in Steel Production (Tata Steel)

Internship & MSc thesis

In a Hot Strip Mill thick steel slabs are hot rolled out to long strips having a thickness range of 2 to 25 mm. After hot rolling the strip needs to be cooled down on the runout Table (ROT) from about 900°C to about 500°C or lower after which the strip is coiled. The new market developments in hot rolled products are mainly in the advanced high-strength steels. These products require a precise and highly flexible control of the cooling path on the runout table. Not only the final temperature (coiling temperature) , but also the cooling rates and intermediate temperatures are important for achieving the right mechanical properties of the steel.

Before a steel strip enters the ROT, there is limited time available for the controller to determine the optimum setup . As there are many variables involved (the settings of each individual bank, material properties, velocity) of which some variables are discrete (e.g. the valve settings: 0%, 70% or 100% open) it is very complex to find the minimum of the objective function within the limited available time: we have about 6 seconds to find the optimum out of  possible control settings. There are various algorithms available, however, many of them are not suitable to find the global minimum (they might find a local minimum as optimum) and/or are not fast enough to be useful. To find a suitable solution, the method must be able to solve a non-convex (having both local minima and a global minimum), non-linear, and discrete problem.

This is a project with R&D at Tata Steel (The Netherlands. For more details and a more detailed problem desciption, please contact Johann Hurink or Marc Uetz.

The Price of Stability for Matroid Congestion Games

MSc thesis

Congestion games are a fundamental model in optimization and game theory, with applications e.g. in traffic routing. The price of stability is a game theoretic concept that relates the quality of the best Nash equilibrium to that of an optimal solution. It is the "smaller brother" of the well known price of anarchy as defined by Koutsoupias and Papadimitriou in 2001, and has been first defined by Anshelevich et al. in 2004. The basic question that is asked here is if and how the combinatorial structure of the strategy spaces of players  influences the quality of the possible equilibria. In that respect, a recent progress was made for uniform matroids and the price of anarchy, which equals approximately 1.35188. The conjecture is that the price of stability for that (and maybe even for more general models) equals 4/3. The proof of this conjecture is the topic of this project. Background literature is a paper by de Jong, Klimm and Uetz on "Efficiency of Equilibria of Uniform Matroid Congestion Games" as well as the more recent paper "The asymptotic price of anarchy for k-uniform congestion games " by de Jong, Kern, Steenhuisen and Uetz. Both papers are available upon request.

For further questions, contact Jasper de Jong or Marc Uetz.

Equilibria for Set Packing Games

Master's thesis 

In a recent paper (de Jong and Uetz, we have analyzed the quality of several types of equilibria for so-called set packing and throughput scheduling games. In that model, players subsequently select items to maximize the total value of the selected items, yet each player is restricted in the feasible subsets she can choose. The results are bounds on the quality of Nash and other game theoretic equilibria. 

One of the distinguishing features of that model is that no item can be chosen by more than one player. That is a natural assumption in sequential games, but appears somewhat artificial when considering single-shot games. 

The question that is to be analyzed in this MSc project is what happens when that assumption is relaxed? First, what type of models adequately model the situation that several players choose one and the same item? And what are the consequences for the resulting equilibria? What is the price of anarchy for pure and mixed Nash equilibria for such a model?

For more information, please contact Marc Uetz.

Sequential Congestion Games and the Price of Anarchy

MSc thesis

In a series of recent publications, several researchers have analyzed sequential games and subgame perfect equilibria in order to circumvent the sometimes bad quality of Nash equilibria. Specifically, de Jong and Uetz (2015) have done that for congestion games with two or three players, showing that the sequential price of anarchy equals 1.5 and 1039/488, respectively. Subsequently, Correa, de Jong, de Keijzer and Uetz (2016) have considered network routing games and showed that -surprisingly- the sequential price of anarchy for games with n players can even be unbounded (while the price of anarchy is only 2.5). All these results are for pure strategy Nash and subgame perfect equilibria.  One of the open questions is what happens if we consider mixed strategies, or settings in which the demand of a player is splittable. As a starting point, one can consider games with two or three players... The underlying research papers are available upon request.

For further information, contact Jasper de Jong or Marc Uetz.

Smoothed Analysis Of High-Dimensional Optimization Problems

MSc thesis
For many optimization problems, finding optimal solutions is prohibitive because the problems are NP-hard. This often holds even in the natural case, where the instances of the optimization problem consists of points in the Euclidean plane. In order to still be able to solve these problems, heuristics have been developed in order to find close-to-optimal in reasonable time. While many such heuristics show a remarkable performance in practice, their theoretical performance is poor and fails to explain practical observations.

Smoothed analysis is a relatively new paradigm in the analysis of algorithms that aims at explaining the performance of such heuristics for which there is a gap between theoretical analysis and practical observation.

Recently, Bläser et al. (Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals, Algorithmica, to appear) have developed a framework to analyze so-called partitioning heuristics for optimization problems embedded in the Euclidean plane. The goal of this thesis is to generalize this framework to higher dimensions and to apply it to analyze further heuristics for Euclidean optimization problems.

For more information, please contact Bodo Manthey.

Brouwer vs. Nash

MSc thesis

In Game Theory we learn that the existence of Nash equlilibria (Nash's Theorem) follows from Brouwer's Fixed Point Theorem. How about the converse? The answer depends on which version of Nash's Theorem we take, but  details must still be clarified. In addition: literature study and overview to see what is known w.r.t. complexity of the two problems (computing fixed points vs. computing Nash equlibria).

Please contact Walter Kern.

Allocations in Simple Games


Let N be a set of n=|N| players. A simple game is defined by a partition of the power set of N into two non-empty sets L and W, W the set of winning coalitions, and L the set of losing coalitions, such that L is closed under taking subsets and hence W is closed under taking supersets. Most well-known are weighted voting games, where each player i in N has an associated nonnegative weight p(i) and winning coalitions W are defined by p(W) being at least equal to 1. To check whether a simple game is a weighted voting game, one is led to consider

For weighted voting games, the min max value is less than 1. In general this ratio may be seen as measuring the distance of a simple game to weighted voting games. For general simple games, a conjecture  states that the optimum is at most n/4.

Assignment: Study particular classes of simple games or try to prove (approximately) the conjecture. Please contact Walter Kern.

Nonseparable resource allocation problems

MSc Thesis

Resource allocation problems are a special type of highly structured mathematical programs. In these problems, the goal is to allocate a given amount of resource (e.g., money, products) over a set of activities (e.g., time) taking into account bounds on the allocated resource for each activity while minimizing a given convex objective function. This problem occurs widely in operations research and engineering (e.g., portfolio optimization, production planning, scheduling, energy management), especially as a subproblem in more complex problems (see Patriksson, 2008 In particular, we are interested in these problems for their application in device modelling in smart grids.

Much research on resource allocation problems focuses on the case where the objective function is separable, i.e., it can be written as the sum of single-variate functions. For this class of problems, many very efficient algorithms are known to solve the problem to optimality. In contrast, little research has been done on the general, nonseparable case, despite its wide range of applications. Recently, we derived a condition on the problem instance that enables us to apply solution methods for the separable version to solve certain nonseparable problems. This project builds on this work and its main goal is to analyze the nonseparable resource allocation problem and derive efficient algorithms to solve (subclasses of) this problem.

For more information please contact Martijn Schoot Uiterkamp.

Integer programming formulations for the traveling tournament problem


The traveling tournament problem is a sports timetabling problem that abstracts two issues in creating timetables: home/away patterns of teams and their traveling. The only compact integer-programming model used in the literature requires O(n4) variables and constraints, where n is the number of teams. Moreover, the LP relaxation is very weak.

You will implement the compact model and another one of size O(n3) in order to compare their strengths and the resulting solver performance. Moreover, you will investigate computationally, whether the weakness of the LP relaxation comes from the scheduling part, the routing part or the combination of both. A final objective is to strengthen the model(s).

Knowledge of Python is required.

For more information, please contact Matthias Walter.

Cutting planes versus strong branching in mixed integer programming


Strong branching is a technique used in mixed integer programming (MIP) solvers. A few iterations of the Simplex method are performed in order to obtain good estimates on the effect of branching on a specific variable.

Another useful technique is the generation of cutting planes, especially for the initial LP relaxation. Some of these cutting planes are obtained by hypothetically branching on a variable. Examples are Chvátal-Gomory cuts, MIR cuts and Lift-and-Project cuts.

The goal of this thesis is to understand how the outcome of strong branching is influenced by cutting planes.

Knowledge of C/C++ is required in order to be able to work with the MIP solver framework SCIP.

For more information, please contact Matthias Walter.

Reverse strong branching


Strong branching is a technique used in mixed integer programming (MIP) solvers. A few iterations of the Simplex method are performed in order to obtain good estimates on the effect of branching on a specific variable.

A new idea, called reverse strong branching, is quite different, but shall achieve the same goals. The goal of this thesis is to complete the idea, implement it within a state-of-the-art solver, and evaluate performance and quality of the approach.

Knowledge of C/C++ is required in order to be able to work with the MIP solver framework SCIP.

For more information, please contact Matthias Walter.