Available master theses in optimization

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


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.


Solution algorithms for the pooling problem

In many industrial applications of network flow problems, such as oil refining and pipeline transportation of natural gas, the composition of the flow is of interest. At the source nodes, flow of different compositions (qualities) is supplied. Flow from the sources is blended at intermediate nodes, referred to as pools. The blending operation is linear, in the sense that one flow unit containing e.g. 1% CO2 blended with one unit containing 5% CO2, yields a blend consisting of two flow units containing 3% CO2. Flow from the pools is blended linearly at the terminals, where bounds on the resulting quality apply. If, for instance, the upper bound at a given terminal is 2% CO2, the flow must be blended such that this requirement is met. Unit purchase costs at the sources and sales revenues at the terminals are defined, and the problem is to find a flow assignment to the network, such that quality bounds are respected, and total net profit is maximized.

It has been shown that this problem, frequently referred to as the pooling problem, is strongly NP-hard, even if there is only one pool. The same is true if there is only one quality parameter (e.g. CO2) subject to upper bounds. In the industry, there is a request for fast solution methods, which does not seem realistic for general instances of realistic size. The focus of the current project is to find fast, possibly inexact, solution methods for the pooling problem. It is also a goal to identify special instance classes that can be solved fast, and to evaluate algorithms for such instances experimentally. The successful candidate has good programming skills and some background in optimization.

Advisor: Dag Haugland.


Order Books, Markets, and Convex Analysis

This project considers how an order market might evolve over a fairly short period - say, during a day. It relies on elementary convex analysis to model agents’ choice of prudent orders, and it explores - by way of computer simulations - whether equilibrium is stable.

Considered is a stylized market for one homogenous, perfectly divisible good. The market remains open during a limited period - say, a day. By assumption, no exogenous shocks occur during the day. To improve their positions, agents repeatedly submit or withdraw orders of moderate size. The latter are posted, picked off, and modified at no cost. Agents are diverse, often anonymous, and typically many. They are self-interested, not without strategic concerns, but somewhat short-sighted. On so weak premises, may repeated trade during the day bring about efficiency at closure time? By way of elementary convex analysis, and computer simulations, this project emphasizes positive prospects. It’s intended to show how little competence agents need to take an order-driven exchange market towards a short-term equilibrium. Most likely, at closure time, the spread in price between the highest bid and the lowest ask is small and stable.
Advisor: Sjur Flåm.


Bilateral exchange

Outline: Motivated by computerized markets, you should consider direct exchange between matched agents, just two at a time. Each party holds a ”commodity vector,” and each seeks, whenever possible, a better holding. Focus is on feasible, voluntary exchanges, driven only by di¤erences in gradients. Your approach should play down the importance of agents’ competence, experience and foresight. Yet, reasonable conditions ought suffice for convergence to market equilibrium.
Advisor: Sjur Flåm.


Efficiency and equal margins

When well defined, the concept of gradient or margin is fundamental in optimization and economics. To wit, for efficient allocation, margins ought coincide across alternative ends and users. Otherwise, scarce resources should be shifted from low valuation (or from inferior yield) to higher.

Traditional use of this good maxim requires though, comparisons of differentials or gradients. For that reason, several questions come straight up: What happens if gradients aren't unique - or, no less important, if a best choice be at the boundary? In such cases, which margins are essential? And how might these coincide?

While addressing these questions, you should illustrate, maintain, refine and extend the said maxim, often referred to as Borch's theorem of insurance.

Advisor: Sjur Flåm.


Call auctions in energy markets

Outline: Many energy markets offer special procedures in order to begin or end ordinary trade more efficiently. Broadly, the early hour ought ease price discovery, whereas the last hour should facilitate execution of still standing orders.

For either purpose, call auctions have been instrumental. Their main feature is that all executable orders should be cleared by uniform linear pricing. Your project is to consider such an auction and elaborate on what an optimizing system operator tends to do. Arguments should revolve around the market opening time - or the period just prior to that event.

Advisor: Sjur Flåm.


Cooperative linear programs

Outline: Consider two linear progams for which the right hand side vectors are in the same space. Merge these program into one. Why might this be advantageous? How should the gains be split?

Advisor: Sjur Flåm.


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: