Assignments (theses)

MSc Thesis

Mathematical optimization plays a large role in the coordination of smart residential energy systems. In these systems, on the one hand, there is an increased infeed of renewable energy (solar, wind). On the other hand, the rising number of electric vehicles, heat pumps, and other “smart devices” leads to an increase of the residential energy demand. This increase is so extreme that it can cause blackouts if not managed properly.

In order to reduce the risk of blackouts, we can reduce peak consumption or production by exploiting the flexibility of smart devices. This is where mathematical optimization comes into play: one can formulate the problem of peak minimization as a mathematical program that can be solved using either standard solvers or, preferably, efficient tailored algorithms.

Within this broad topic, there are several possibilities for MSc theses. Following are three examples of research projects:

• In our optimization models, we make many assumptions on the properties of devices in order to obtain efficient (i.e., polynomial-time solvable or convex) models. Examples of this are continuous charging behavior, minimal losses, and perfect state-of-charge measurements. To what extend can these assumptions be relaxed while maintaining the efficiency?
• The (electricity) distribution grid has a hierarchical network structure with different levels. At the bottom of the hierarchy are consumption devices and local energy production devices (e.g., solar panels), whereas higher in the hierarchy are larger grid assets such as transformers. Due to this level structure, peak reduction on all levels is required in order to maintain a proper grid operation. When only two levels are considered, this can be done relatively efficiently. However, as soon as more levels are included, the efficiency decreases drastically due to the increased dimensionality. How can we increase the scalability of peak reduction strategies applied to multiple network levels?
• One approach to tackle peak consumption or production is by introducing a clever market design. This market structure should be such that everyone is incentivized to participate in reducing the peaks. Existing literature makes extensive use of tools from the area of (Algorithmic) Game Theory. Up to now these approaches differ in many aspects, such as the variety of smart device types, their stability, and their running time. Is there a way to combine the advantages of these approaches or generalize the setting even further (for instance, include uncertainty)?

For more information, please contact Johann Hurink.

MSc Thesis

The hyperball algorithm, based on probabilistic counters, turned out extremely effective and efficient in computing graph distances in gigantic networks, such as Facebook. In this project we will investigate what other important characteristics of networks can be estimated using this powerful method.

In particular, we focus on the important problem of minimizing conductance: a measure for how well-connected a group of vertices is to the rest of the network. Conductance has many important applications: it gives information on how fast a rumor spreads through a network and it can help in finding ‘communities’, sets of densely connected vertices within a graph. These communities usually have low conductance, and finding good communities then translates to finding sets of low conductance.

However, finding a set of minimum conductance in a graph is computationally intractable. We will investigate whether we can efficiently find good candidates for sets of minimal conductance using hyperball-type algorithms.

For more information please contact Clara Stegehuis

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.

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.

MSc Thesis 

In a recent paper (de Jong and Uetz, https://arxiv.org/abs/1709.10289) 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.

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.

MSc Thesis

In the future electricity grid with high penetrations of renewable energy and electric vehicles, we may risk grid overloading and possibly even blackouts. By providing incentives to producers and consumers of electricity, they may change their behaviour such that these problems are prevented.

A complicating factor is that overloading depends on the total loads in the network in a non-linear way. The main task for this assignment is to study and design suitable price functions or mechanism using game theory.

We would like to know if there is an incentive scheme that gives an efficient Nash equilibrium under some realistic assumptions.

This thesis will be jointly supervised by Alexander Skopalik (MOR) and Marco Gerads (CAES)

MSc Thesis

Swarms of drones are often used to track targets. Examples range from tracking criminals in cars by the police to tracking sports players to create live footage. Drones can track these objects easily without creating disturbance, as they can move in space.

To track an object, multiple drones measure their distance to the object, and then together calculate the position of the object. Drones know their own position through GPS measurements. However, these GPS measurements may not be completely accurate, so that drones only know their position with some error. When they position their distance to the target, this means that the position of the target also becomes more uncertain. Based on this uncertain information, the drones have to decide where to move to keep the object in sight. The drones only have a limited angle of sight, and therefore a wrong decision can cause the drones to lose the target.

So where should we deploy the drones to create a robust strategy that minimizes the probability to lose the target? And if we lose the target, can we come up with a strategy to find it back? In this assignment you will take the probability distribution of the drone locations and their errors into account to determine the optimal strategy to track their target.

This project will be jointly supervised by Clara Stegehuis (MOR) and Anastasia Lavrenko from Electrical Engineering.

For more information about this final project, please contact Clara Stegehuis.

Social robots have been used in a number of fields. The UT has had projects that studied the use of these robots in fields like care / cure (ProSPEro, DeEnigma), education (EASEL), police work (R3D3) and even art (Kunst- en Techniekwerk). Across the world, similar projects have carried out studies with available platforms in even more domains, but overall performance remains unsatisfactory because interaction is not fluent and responsive enough to maintain long term appeal. For example, the PRoSPEro project found that care workers who are introduced to working with robots start out having high expectations, after a while report disenchantment with the very limited repertoire of tasks and behaviours that it supports. This leads to the robots not being used so much in the longer term. To improve this situation, social robots that interact with (groups of) people must be expressive in a responsive way.

One of the challenges that needs to be addressed when designing such robots (we believe) is of an algorithmic nature. A expressive social robot needs to show a mix of active, reactive and reflexive behaviour. However, those behaviours will be in constant conflict with each other, as some tasks cannot be performed in parallel. For instance, a robot cannot look at two different people at the same time and trying to do so might result in a robot that is cross-eyed. Thus, an algorithm should choose in real time if the robot first looks at one person and then at the other or, perhaps, that it only looks at one and ignores the task of looking at the other.

During this project, you are expected to develop a model that provides a good basis for an algorithm to make scheduling decisions of behavioural tasks of a robot. Subsequently (and likely in parallel), you develop and analyse (an) algorithm(s) that can make these decisions in an online fashion. Ideally, you will implement your algorithm(s) to test on a real robot.

For this project you should have followed the course Scheduling and you should have an affinity for computer programming.

The project will be carried out under supervision of Ruben Hoeksma and Edwin Dertien from the Robotics and Mechatronics group (Electrical Engineering).

For more information please contact Ruben Hoeksma.

The ultimate goal of topics in this area is the extension of the software library CMR (Combinatorial Matrix Recognition) that contains efficient implementations of recognition algorithms for several classes of matrices. Final projects can involve the following things:

• Experimental implementation of recognition algorithms (graph or matroid theory, Python programming).
• Study of recognition problems, (graph or matroid theory, algorithms).

For those with programming experience in C or C++ there is another option possible:

• Implementation of algorithms for the CMR library.

If you find one or more of these topics interesting, please contact Matthias Walter.

There are various topics available in the broad area of mixed-integer programming (MIP). There are topics about general-purpose MIP, but also those related to concrete applications such as:

• Production scheduling (machine scheduling)
• Network design (transportation)
• Physics (Low Auto Correlation Binary Sequences, ground state of Bernasconi model)
• Cryptanalysis

Besides concrete application, foundational topics are also available:

• Quadratic variants of combinatorial optimization problems
• Binary polynomial optimization (products of binary variables)

Irrespective of the potential application, there are different sorts of research that can be carried out:

• Modeling a problem via MIP forms the basis, but alone is not considered a sufficient contribution for a final project.
• Find new inequalities to strengthen a formulation (often requires to run code on a console to find these).
• Prove facetness of inequalities.
• Develop separation (=row-generation) algorithms.
• Prove perfection of a formulation (often for a subproblem or relaxation).
• Evaluate bound improvement computationally (requires Python).

For those with programming experience in C or C++ there are even more directions possible:

• Integrate new inequalities in a state-of-the-art MIP solver.
• Implement decomposition approaches such as Benders' or Dantzig-Wolfe decomposition.

If you find one or more of these topics interesting, please contact Matthias Walter.

The traveling salesperson problem (TSP) is a classical NP-hard optimization problem. The task is to find a Hamilton cycle (tour) of minimum length through an edge-weighted graph. TSP has a huge variety of applications and even serves as arguably the most popular benchmark problem to try out techniques in optimization.

A very popular heuristic to hopefully find close-to-optimal solutions quickly is a simple local search heuristic called k-opt: Given a tour, remove k edges and replace them with k edges such that the result is again a tour, if this shortens the total tour length.

While in particular 2-opt performs very well in practice, both in terms of quality and in terms of efficiency, it is extremely slow in the worst case. Only recently, efficient restricted variants have been analyzed more closely.

The goals of this thesis is to adapt and analyze efficient variants of k-opt for the asymmetric TSP and the Euclidean TSP.

If you are interested, please contact Bodo Manthey.

Due to the ongoing energy transition and the associated electrification, there increasingly are problems on the electricity grid. One of these problems is congestion, which occurs when too much current is flowing through the cables in the grid, which leads to overheating of equipment and voltage violations. Currently, in more than half of the Netherlands, medium and large grid-users can no longer be connected to the electrical grid due to congestion associated risks. This means that new hospitals, schools, and apartment buildings can no longer be connected to the electrical grid, and existing businesses cannot electrify since they cannot upgrade their electrical grid connection.

A promising way to alleviate electrical grid congestion is through the use non-firm connection limits. A connection limit is the maximum allowed consumption and production of a grid-user. If a grid-user has a non-firm connection limit, it means that the grid-operator can change the maximum allowed consumption/production of that household. For example, a grid-user might normally be allowed to consume 100kW, but the grid operator can temporarily decrease this to 70kW. If the grid-operator forecasts congestion near this grid-user, the grid-operator can decrease the connection limit to decrease this congestion.

Every fifteen minutes the grid operator makes an energy-consumption forecast for every point in the grid, and based on this determines if there is congestion in the grid. If there is congestion, the grid-operator needs to intervene by changing the connection limit for grid-users with a non-firm connection limit. However, if there are many non-firm connection limits in the grid, which subset do you choose?

For this project, you will develop an algorithm that determines at which nodes the grid-operator should change the connection limit to eliminate congestion while minimizing costs for the grid operator and while keeping user satisfaction high. Proposed approaches are bin-packing-inspired algorithms, metaheuristics such as simulated annealing, or mathematical programming formulations such as optimal power flow. You will also need to consider practical constraints, for example, the proposed algorithm needs to finish in minutes.

A dataset containing an electrical grid network structure will be provided, as well as the associated energy consumption/production at each node in the network. Prior knowledge about electrical grids is not required, and the student will receive sufficient guidance when learning the required background knowledge.

If you are interested, please contact Flin Verdaasdonk.

Cycling behavior is influenced by how people think and process information. When your brain is overloaded, it becomes harder to focus and perform tasks. This can affect how cyclists ride their bikes, especially in complex traffic situations. Which brain regions connect and work together while cycling? And how does this depend on the complexity of the traffic situation?

In this thesis, you will investigate how brain activity changes during cycling in different traffic conditions, using data collected through a method called functional near-infrared spectroscopy (fNIRS). This method measures the oxygen levels in different parts of the brain to see which areas are active. The answers from this thesis can give us insight into how cyclists process information and handle mental challenges, helping us better understand their performance in traffic.

If you are interested, please contact Clara Stegehuis. This thesis is in collaboration with Baran Ulak (Civil engineering, bike safety)