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 Nelly Litvak or 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.

MSc Thesis

Matroid Matching (also known as linear matroid parity) is a generalization of matchings (in nonbipartite graphs) and matroid intersection. Recently, an algorithm to solve the weighted version in polynomial-time was devised for the case of matroids that are derived from a matrix.

There is a straight-forward integer linear optimization formulation for the problem. The recent algorithm shows that solving the integer program is tractable. We are now interested in an LP description of the problem, i.e., the convex hull of the solution vectors.

The first step of the project is to study (the small amount of) existing literature on this matroid matching polytope. One of the known results is an LP formulation in terms of additional variables if the underlying matroid is of a special type. In this case, the polytope is in fact the projection of some matching polytope. Consequently, the second step of the project is to describe the projection of this matching polytope in the original space, i.e., to project out the auxiliary variables. In a third step, further missing inequalities (for the general case) can be derived with the help of computer programs. Their structure shall be described mathematically.

Knowledge from the Mixed-Integer Optimization course is required.

For more information, please contact Matthias Walter.

MSc Thesis

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++ and from the Mixed-Integer Optimization course is required in order to be able to work with the MIP solver framework SCIP.

For more information, please contact Matthias Walter.

MSc Thesis

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++ as well as from the Mixed-Integer Optimization course is required in order to be able to work with the MIP solver framework SCIP.

For more information, please contact Matthias Walter.

MSc Thesis

One approach for solving the graph coloring problem works by encoding the color classes in a binary decision diagram (BDD). Once such a BDD (or a relaxed version of it) is available, the graph coloring problem can be modeled as the problem of finding the smallest number of source-sink-flows in the BDD subject to certain covering constraints. This modified "flow cover" problem (FC) was not studied in the literature so far.

The goal of this problem is to use existing code for creation of BDDs to investigate cases where the natural LP relaxation of (FC) is not integral and find classes of cutting planes in order to strengthen it. After finding such inequalities with the aid of software, they must be understood mathematically and facetness shall be analyzed. Finally, the complexity of the separation problem may be investigated, e.g., hardness proofs, separation algorithms or heuristics.

Knowledge from the Mixed-Integer Optimization course is required, basic experience with a Linux console may be helpful.

For more information, please contact Matthias Walter.

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.

MSc Thesis

We consider a formulation process from the chemical industry. A set of orders shall be processed on different types M₁, M₂, M₃ of machines within a minimum makespan. Each job is first processed on one of several so-called formulation lines (M₁) after which it may be stored temporarily in one of several buffers (M₂) before finally getting processed in one of several filling machines (M₃). The complexity arises because of different types of filling machines, a limited number of buffers and the fact that machines require cleaning time whenever the processed fluid is about to change.

Since direct mixed-integer programming models are prohibitively large, decomposition approaches such as Dantzig-Wolfe Decomposition or Benders' Decomposition shall be investigated. One possibility is to exploit the fact that for fixed combinatorics (i.e., job ordering and assignment to machines) the problem of computing the makespan can be solved via Discrete Event Simulation, which is algorithmically well-understood. Due to the industry collaboration, data for this problem can be made available to test the approaches for real-world scenarios.

Knowledge from the Mixed-Integer Optimization course is required.

The project is jointly supervised by Matthias Walter (DMMP), Meik Franke (SPT) and Roderich Wallrath (SPT and Bayer AG).

MSc Thesis

Consider a mixed-integer program with variables x. Frequently, modelers want to model for a certain subset J of the variables that x_J must be a among a certain vectors y₁, y₂, ..., y_k that are known explicitly. This requirement can modeled in several ways, and inexperienced modelers frequently come up with very creative but ineffective techniques. For example, researchers in cryptanalysis tried to model this via as few linear constraints as possible, which gave small linear programs but very weak relaxations.

The goal of the project would be to create a plugin for the MIP solver framework SCIP to which these vectors are supplied, and which can apply several different techniques to realize the constraint.

Knowledge from the Mixed-Integer Optimization course and experience with C/C++ is required in order to be able to work with the MIP solver framework SCIP.

For more information, please contact Matthias Walter.

MSc Thesis

We want to minimize a polynomial p(x) over x in {0,1}ⁿ. After an appropriate linearization the problem can be addressed by optimizing over the multilinear polytope, which is defined for every hypergraph (that depends on the structure of p). In order to improve this approach, further valid inequalities for this polytope shall be found. Moreover, effective algorithms for solving the separation problem shall be studied.

The project allows to specialize into both, theoretical as well as practical directions. For instance, facetness or completeness of relaxations can be investigated. Alternatively, an existing implementation of separation algorithms within the MIP solver framework SCIP (requiring C/C++ knowledge) are possible.

For more information, please contact Matthias Walter.

MSc Thesis

The low auto-correlation binary sequences problem is about finding sequences x in {-1,+1}ⁿ such that a certain degree-4 polynomial is minimized. The so-far most successful work for computing such sequences for small n is by exhaustive search. The goal of the project is to improve a new promising integer programming formulation for the problem, e.g., by adding problem-specific cutting planes (which must be developed during the project).

For more information, please contact Matthias Walter.

MSc Thesis

For mixed-integer optimization one can easily model products of variables x_i and x_j by introducing auxiliary variables y_ij and linearizing the product. This, however, can lead to a blow-up of the formulation, e.g., for the quadratic assignment problem such a formulation would have O(n⁴) variables (in contrast to the O(n²) original assignment variables). Often many such variables appear with the same coefficient in the objective. One idea is to introduce an auxiliary variable z for the sum of (some of) such y-variables and project out the latter. The development for descriptions for such formulations by means of linear inequalities are the subject of this project.

For more information, please contact Matthias Walter.