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.

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.