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.
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.
Opimal 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.
Fast methods for solving a network flow problem with quality constraints and minimum lot sizes
In many types of transportation networks, such as pipeline networks for transportation of natural gas, flow qualities are defined at the sources, and flow quality bounds are imposed at the terminals. The sources, typically represented by gas wells, provide flow of unequal compositions. For instance, some sources may be richer on undesired contaminants, such as CO2, than others. At the terminals, constraints on the relative content of the contaminant may be imposed. To account for the quality bounds at the terminals, the quality therefore must be traced from the sources via junction points to the terminals.
It is often impractical to send across amounts of flow below a lower threshold, referred to as the minimum lot size. In such instances, the problem becomes much more difficult to solve, and exact methods tend to be too time consuming for practical use. In this master project, the candidate will develop and implement fast methods for the said problem. It is not generally required that the methods provide the optimal solution, but verification of the solution quality is essential. Such verification will be made experimentally by comparison to the exact solution in instances where the solution is known, and by comparison to solution bounds in instances where the solution itself is not available.
Because of the experimental nature of this project, a substantial part of the work will be computer implementations, preferably in C++ or Java, of the suggested methods.
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:
Sist endret: 14.3.2013