Available master theses

Source to Source Code Transformation

Source to Source Code Transformation takes as input a computer code and generates a new code. The type of codes we consider are computer program that takes as input some parameters and generate some numbers. An example could be computing the values of a function at a specific point. The source code is transformed to also include computation of the derivative. There are many different systems available depending on the computer language like ADG, ADIFOR, TAPENADE, ADOL-C, but we will focus on TAPENADE. See http://www.autodiff.org/ for an introduction to automatic differentiation and an overview of programs.

In this master project we will use the transformation in a recursive fashion: the transformed code is transformed again to compute the second derivative. We will study the efficiency of this approach and the effect of the data structure for storing the derivatives.

Advisor: Trond Steihaug
Background: Enough calculus to know what the Jacobian and Hessian matrices are.  See the following YouTube  http://www.youtube.com/watch?v=a9P5Ql-A7pM

 

On Multi-Subdomain Optimization Problems

In this project we consider nonlinear optimization problems with varying objective functions. More precisely, we consider a grid over a given domain with n attributes assigned. The aim is to determine a min-max number of grid points (subdomains) such that the variance (or any measure of it) of each attribute is some acceptable optimal value. The restrictions refer e.g. to given costs and time constraints. The optimization problems under consideration arise from a mathematical model which is used in fishery research; the objective function can e.g. be related to optimal trajectories of fishery ships. This master thesis project will be developed in cooperation with the Institute of Marine Research in Bergen. In this project the candidate will study the mathematical models used, and apply appropriate optimization techniques to them. The latter part refers to efficient implementation of solution techniques and calculating numerical solutions.

Advisor: Jan Rückmann

 

Optimization Methods in Finance

The use of mathematical optimization methods in finance is common-place and a continuously developing vivid area of research. These methods are used for many different tasks: for pricing financial products, estimating risks, determining hedging strategies, and many others. The goal of this project is to study how optimization techniques - such as linear, quadratic, and nonlinear programming, robust optimization, dynamic programming, integer programming, and others - can be used in the framework of mathematical finance.

In this project the candidate will study recent models from mathematical finance which are using mathematical optimization techniques. Furthermore, corresponding solution methods will then be applied numerically to some particularly chosen models. The latter part refers to efficient implementation of solution techniques and calculating numerical solutions.

Advisor: Jan Rückmann

 

Cable Layout in Offshore Windfarms

In an ongoing master project in optimization, the following problem is studied: For offshore wind farms given by

  • GPS coordinates of the wind turbines,
  • GPS coordinates of the target point(s) of the supply cable(s),
  • GPS coordinates of areas prohibited for cables,
  • number of substations and/or GPS coordinates of the substations,
  • maximum number of wind turbines per cable string or loop,
  • whether the cables should loop to provide redundancy,
  • whether substations should be connected by export cable to provide redundancy,
  • whether the wind turbines can have more than two neighbours and if so, the cost induced by additional neighbours,

we look for the cable layout minimizing the total cable length. In the suggested thesis, we shall study extensions of this problem. In the first extension, we assume that a cable route can be split at specific turbine locations (network nodes). The split comes with a cost, depending on the number of splits that are made (the node degree). Further, we will take into account the trenching costs. Cable links will be laid in trenches in the sea bed, and two or more links can share the same trench. Subsea trenching is extremely expensive, and substantial saving can be achieved by restricting the total length of the trenches. Thus, the second extension is to find one trench route and one cable route as well as an assignment of cables to trenches. The objective is to minimize total costs.

Possible thesis work activities include mathematical modelling, theoretical analysis, design of smart (exact or inexact) solution methods, and efficient implementation.

Advisor: Dag Haugland.

 

Strong formulations for power-minimizing trees in ad hoc wireless networks

Given a simple graph with edge weights, the well-known minimum spanning tree problem amounts to finding a tree covering all vertices of the graph such that the total weight of the edges in the tree is minimized. Since the objective function is so simple, a function of weights of selected edges, the problem can be solved very fast. An application of the minimum spanning tree problem is the problem of designing a wired communication network, connecting a set of clients in such a way that the total wire length is minimized.

When moving from a wired to a wireless technology, the problem of connecting clients in a rational way becomes more complicated. In wireless ad hoc networks, two devices can communicate directly only if the transmission power of the sending device is sufficiently high. A commonly-used optimization criterion for a tree connecting all the devices, is that the total power is minimized. This leads to the problem of finding spanning trees with a more complicated objective function than what is the case in the traditional minimum spanning tree problem. The main difference is that rather than all edges in the tree, only a subset of them contribute with their weight in the objective function.

Depending on what wireless technology is used, the objective function can be a sum of the following edge weights:

  • For all vertices, the largest weight of incident edges.
  • For all vertices, the largest and second-largest weights of incident edges.
  • Assume the tree is rooted in one dedicated source node. For all nodes except the leafs in the rooted tree, the largest weight of leaving arcs.

It is known that finding the spanning tree with minimum total weight is NP-hard in each of the cases Several discrete optimization models have been suggested, and the most promising ones seem to be those based on the principle of multi-trees. The nice feature of these models is that when binary variables are replaced by continuous ones, they still take binary optimal values in many instances.
This means that the instance can be solved by linear programming.

Another interesting observation about multi-tree models, is that they can be generalized to even stronger models. In fact, a sequence of generalized multi-tree models seem to be achievable, and it is likely that the strength of the models is increasing in the sequence.

In this project, the candidate is to analyze generalized multi-tree formulations for one or more of the spanning tree problems outlined above. It is also relevant to study how the generalized models work on the much more studied Steiner tree problem, which amounts to finding a tree of minimum wight spanning a given subset of the vertices of the graph.

The exact content of this project will depend on the interests and qualifications of the candidate. It is possible to define it such that its main part is on computer implementations. However, the questions to be addressed are partly of a theoretical nature, and the project may offer substantial theoretical challenge to interested candidates.

Advisor: Dag Haugland.

 

Optimal portfolio selection with minimum buy-in constraints

Investors in charge of selecting the assets to constitute a portfolio, will typically use the expected return as a measure of the expected value, and the variance as a measure of the risk. To keep operational costs down, the investors may impose certain constraints on the portfolio selection. For instance, they may require that the volume of any selected asset must be at least a given fraction of the total portfolio.

In this thesis, the candidate will study mathematical models and efficient solution techniques for such problems.

Advisor: Dag Haugland.

 

Flexible datastructures in C#,  Java and c++

In a master thesis we derived a new datastructure using array of arrays in c# and Java for sparse matrices. Array of arrays is also a possible contruction in c++. This master thesis project combines the ideas of sparse matrix structures and the matrix determination problem. For the matrix determination problem we will use the c++ package DSJM or ColPack.  For information on the datastrukture JSA see http://www.ii.uib.no/forskningsgrupper/opt/forskning/Home_JSA/jsa.html.

Because of the experimental nature of this project, a substantial part of the work will be computer implementations, preferably in c++.

Advisor: Trond Steihaug.

 

Self-defined master thesis in optimization

Often, new master students have a suggestion for a master thesis. Their idea might for example be based on their interests, or they have heard of a problem with a background in an (for example industrial) application by someone they know. Students with such a suggestion are very welcome to present their idea to the appropriate group at the department.

Master students in optimization are offered very interesting theses within a broad range of applications and techniques. Several theses have industrial applications in e.g. oil and gas, telecommunications or fisheries. The projects typically involve modelling, analysis, development of new solution methods, implementation and experimentation. For most theses, good programming skills are required.

Work on a master thesis usually falls into one or more of the following categories:

  • Modelling: Design an optimization formulation based on the description of the problem. The formulation is implemented, and the aptness of the formulation for solving the problem is examined experimentally and possibly theoretically.
  • Algorithm design: Design an algorithm to solve a specific optimization problem. The algorithm is implemented, and used to solve the problem with datasets of varying size.
  • Algorithm analysis: Theoretically and experimentally compare several algorithms designed for solving a specific optimization problem.

Problems usually fall into one of the following areas:

  • Linear programming
  • Integer programming
  • Combinatorial optimization
  • Non-linear programming
  • Parameter estimation

Students with a suggestion for a thesis meeting the above description, are very welcome to contact a member of the optimization group and present their idea. For further information about master theses in optimization, please contact: