Master Theses

open theses

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.

Fast methods for solving the pooling problem

In pipeline transportation of natural gas, simple network flow problems are replaced by hard ones when bounds on the flow quality are imposed. The sources, typically represented by gas wells, provide flow of unequal compositions. For instance, some sources may be richer on undesired contaminants, such as $CO_2$, than others. At the terminals, constraints on the relative content of the contaminant may be imposed. Flow streams are blended at junction points in the network, where the relative $CO_2$-content becomes a weighted average of the relative $CO_2$-content in entering streams. To account for the quality bounds at the terminals, the quality therefore must be traced from the sources via junction points to the terminals.

The problem of allocating flow at minimum cost is referred to as the pooling problem when the above-mentioned quality bounds are imposed. It is known that the pooling problem is NP-hard, which means that it is very unlikely that exact solutions can be found in instances of large scale. Some exact methods, based on strong mathematical formulations and intended for instances of small and medium size, have recently been developed. However, the literature offers few approaches to approximation algorithms and other inexact methods dedicated for large pooling problem instances.

In this master project, the candidate will develop and implement fast methods for the pooling 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. Theoretical verification, in terms of e.g.\ error guarantees, may turn out to be difficult for some of the methods. For the simpler methods, however, the candidate will be encouraged to elaborate also on this.

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.

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.

In optimization, appropriate suggestions usually meet 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
Estimation of prameters

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.

ongoing theses

Design of floating wind turbines

In a pilot project, Statoil recently installed the Hywind turbine in the North Sea, as the first operational large-capacity floating turbine worldwide. Hywind thus proves technological feasibility of floating turbines. Unfortunately, the installation costs of the project are currently too large to be covered by the return from the energy produced by the turbine. To make floating turbines commercially competitive, a methodology for maximizing the net return per invested monetary unit becomes crucial.

In this project, we study how this can be approached by a computer implementation of a mathematical optimization model. When designing the tower to carry the wind turbine, a number of requirements must be respected. Noteworthy among these is the constraint that the tower is stable when exposed to wind and wave forces. Another important constraint is that the expected life time of the construction is sufficiently long. Finding a design respecting all such requirements, and such that the costs are minimized, is a complicated optimization problem. It involves mathematical modeling of all relevant constraints, and developing algorithms that can solve the models.

Currently, the Optimization group at Department of Informatics and Statoil are collaborating on the development of a methodology as described above. In the suggested master project, the candidate will be engaged in this collaboration. The work will involve the following activities:

Mathematical modeling: Make a selection of decisions (typically dimensions of the unit carrying the turbine) and constraints (typically stability and endurance constraints as explained above) to be included in the model. Express the relations between decisions and costs and between decisions and constraints in terms of equations and inequalities.
Solution methods: Finding available solution methods suitable for the proposed model, and/or extend these into new ones.
Implementation: Use of software tools, such as GAMS for the modeling part and MINOS/BARON/MATLAB for the solution algorithms. Programming in C++ or Java for implementing new algorithms.
Experiments: The models are run on real data, and different approaches are compared.

Advisor: Dag Haugland.

Student: Surbhi

Enrolled semester: Fall 2010

Optimal layout of offshore wind farms

When an air flow meets a solid body, such as a wind turbine, the flow becomes disturbed in the downstream vicinity of the turbine. The region where this effect is significant is referred to as the wake.
In a wind farm consisting of several turbines, the power outtake from any individual turbine thus depends on its position relative to the wakes of other turbines.

In this master project, the candidate will develop a mathematical model for optimizing the utilization of an offshore field allocated for (floating) wind turbines. One important component of the model, will be a unit that estimates the wake generated in the wind farms. On top of the wake unit, an optimization unit that trades costs against total power outtake must be developed. Decisions to be supported by initial versions of the mathematical model should include the location of individual turbines and cable routes between them.

While the demand for a high power production calls for a large number of turbines, the considerable installation costs, in addition to operating and maintenance costs, suggest the converse. To keep cabling costs low, a dense farm covering a small area is favorable to a scarce one, whereas undesired wake effects are lesser in a field scarcely populated with turbines. Interrelations between turbines, such as power losses due to wake, will be captured by the wake unit. Recognizing these interrelations, the optimization unit will find the turbine locations and cable pattern that maximize the net profit, defined as the economic value of power generation minus total costs.

The indicated location problem is likely to represent great computational challenge. It is therefore necessary that the wake unit is relatively simple, although it must be sufficiently precise in order to reflect the relations between turbines in a realistic way. The existing literature offers some suggestions to wake models, and the candidate must evaluate some of these, and hence find a wake model suitable for the project. The thesis work will involve the activities:

Literature review on simplified wake models: Find a wake model that is suitable for integration with an optimization model for turbine locations in offshore wind farms.
Mathematical modeling: Design the optimization unit and its integration with the wake unit.
Solution methods: It is unlikely that model instances of realistic size can be solved very fast. Therefore, the candidate should develop methods that quickly give approximate solutions.
Implementation: Use of software tools, such as GAMS for the modeling part and e.g. BARON for solving the model. Programming in C++ or Java for implementing new algorithms.
Experiments: The models are run on real data, and different approaches are compared.

Advisor: Dag Haugland.

Student: Jan Kristian Haugland

Enrolled semester: Fall 2010

Modeling Vertical Fish Migration

The aim of this project is to model the vertical migration pattern of fish, using an SDE (stochastic differential equation approach). We intend to address ecosystem questions, such as,
• Are there ecosystems–specific preferences for depths/temperatures?
– This should come from the data analysis
• Can we detect seasonal variations (summer/winter), and influence by e.g., sunlight?
– This should come from the data analysis
• Based on modeled vertical migration patterns of fish, can we speculate on the effect of
– Global warming (temperature gradients steeping) on vertical water column usage? – assuming all other parameters remaining invariable. What are the uncertainties?
– Can we distinguish between fish from two ecosystems, or two different fish species from the same ecosystem, based on the SDE parameters?
The aim is to limit the thesis to data derived from tagging of Northeastern Arctic Cod and Norwegian coastal cod. For each species, there will be 2 data sets for modeling, and a third data set for validation.

Advisor: Sam Subbey and Dag Haugland.

Student: Erik Natvig

Enrolled semester: Fall 2010

Interior-point methods for network flow problems

The first practical method for solving Linear Optimization (LO) LO-problems was the simplex method, proposed by Dantzig, in 1947. This algorithm explicitly explores the combinatorial structure of the feasible region to locate a solution by moving from a vertex of the feasible set to an adjacent vertex while improving the value of the objective function. Since then, the method has been routinely used to solve problems in business, logistics, economics, and engineering. Klee and Minty, have shown in 1972 that the simplex method goes through 2n − 1 vertices. This shows that the worst-case behavior of the simplex method is exponential.

In 1984, Karmarkar proposed a new polynomial-time method for solving linear programs. This method and its variants that where developed subsequently are now called Interior point methods (IPMs). After an initial controversy it has been established that for very large, sparse problems, subsequent variants of Karmarkar’s method often outperform the simplex method. The study of Interior-Point Methods is currently one of the most active research areas in optimization. The name “interior-point methods” has originated from the fact that the points generated by the algorithms all lie in the interior of the feasible region. This is in contrast with the famous and well-established simplex method where the iterates move along the boundary of the feasible region from one extreme point to another. Nowadays, IPMs provide a powerful
tool for solving Linear Optimization (LO) problems. They become an alternative to the simplex based methods and are particularly useful in applications where the size of the problem is very large. Moreover, it turned out that the IPM-approach to LO has a natural generalization to the related field of convex nonlinear optimization, which resulted in a new stream of research and an excellent monograph of Nesterov and Nemirovski 1993.This monograph opened the way into other new subfields of optimization, like semidefinite optimization and second order cone optimization, with important applications in system theory, discrete optimization, and many other areas.

The aim of this project is to design and explore the use of IPM-algorithms (path-following, predictor-corrector) or Infeasible interior point algorithm for network flow problem in practise. The project is a combination of mathematical analysis, numerical optimization and computer science.

We deal with project as follows: Part 1) Design IPMs for special network flow problem (network flow problem that can be formulated as a linear optimization problem). Part 2) Develop a practical variant of an IPM solver for network flow problems that are not linear. Of special interest and practical relevance is the pooling problem, which is a network flow problem that frequently occurs in industrial applications like oil refining and pipeline gas transportation.

Advisors: Mohamed El Ghami and Trond Steihaug

Student: Doaa Hassan (part time)

Enrolled semester: Fall 2009

completed theses

Solving system of nonlinear equations using methods in the Halley class, Sara Tagelsir Mohamed Suleiman , 2009
Automatic Differentiation of Third Order Derivatives using Forward Mode in C++, Torbjørn Lium, 2009
A matrix-free method for regularisation with unrestricted variables, Bjørn Harald Fotland, 2008
Improving Efficiency in Parameter Estimation Using the Hamiltonian Monte Carlo Algorithm, Mohammed Ali Albashir Alfaki, 2008
Optimal gasstransport i rørledningsnettverk, Frode Lidal, 2008
Grafpartisjonering med GRIBB, Brage Breivik, 2006
Heuristikker for Traveling Salesman Problem ved dekomponering av kostmatrisen, Espen Skippervik Sætre, 2006
Solving the Traveling Salesman Problem with GRIBB, Andreas Angerman, 2005
Comparing methods for dictionary-based representation of images and video, Øyvind Listou, 2004
Frame based heuristics for signal representation, Lars Berntsen, 2004
En visuell tilnærming til simulering av købaserte modeller i Java, Morten Johannes Ervik, 2004
Heuristics for a Stochastic Vehicle Routing Problem, Lars Magnus Hvattum, 2003
Preprocessing of large scale linear systems, Bernt Asbjørn Omland, 2003
Heuristics for the Set Partitioning Problem, Christian Berg, 2003
Metoder for direkte volumvisualisering av to overlappende volumer i sanntid, Frode Røsjø,2003.
Sanntids 3D urbanmodellering, Bjørn Gisle Hodneland, 2003.
Optimal adjustment of surfaces to points in three-dimensional space, Ole Kåre Endresen, 2003
Discrete event simulation in Java with applications in rodent navigation, Ørjan Bergmann, 2002
Inexact Solution of the Schur Complement Equation in a Primal-Dual Interior-Point Method for Semidefinite Programming, Lennart Frimannslund, 2002
The use of Java Arrays in matrix computation, Geir Gundersen, 2002
Ein modell for ressurstildeling i stokastisk prosjektplanlegging, Ingrid Honve, 2002
Optimal and Heuristic Solutions in the Transhipment Problem, Lars Magne Nonås, 2002
Automatic Differentiation in Java, Rune Skjelvik 2001,
Event-related functional Magnetic Resonance Imaging (fMRI) of the brain: Models and estimation of the Haemodynamic BOLD response, Inger Helen Khateeb, 2001
Visualisation with database connectivity through a network-aware environment, Jannike Utheim, 2000
Solving Vehicle Routing Problems using Lasso Solutions, Nils Tjøstheim, 1999
Visualization and manipulation of small scale archaeological artefacts, Tom Bech, 1999
Three dimensional image restoration of magnetic resonance (MRI) head volumes, Bjørn Hamre, 1998
Forenklet pålogging til Telenors interne dataressurser, Eva-Cecilie Lossius, 1998
Utvikling av prediksjonsmodeller ved hjelp av heuristisk søk, Arild Hoff, 1998
Three dimensional visualization of structural and functional magnetic resonance imaging data from the human brain, Pål Magne Hisdal, 1998
Monitoring and visulaization of distributed systems, Demissie Bediye Aredo, 1998
Primal dual interior point method using an iterative solver for the linear system, Venansius Baryamureeba, 1996
Konvergens av en iterative løser av LCP, Gøran Espeland, 1996
Refitting og reversert refitting av flintstein, Jostein Sætherø, 1995
Asynchronous solution of linear least squares problem using generalized group iterative methods, Yasemin Yalçinkaya, 1995
Datafitting problem, Wenli Wang, 1994
Software for estimating sparse Jacobian matrix by row and column partitioning, Jian Da, 1994
Trunkert indre punkt metoder for lineære optimeringsproblemer, Erik Spildo, 1994
Mathematical programming in capital budgeting, Reidun Helming, 1994
Aggregering av lineære problemer, Sigrid Lise Nonås, 1993
Kurvetilpasning med interaktiv datagrafikk og preferanseoptimering, Lars Magnus Nordeide, 1993
Estimation of sparse Jacobian matrices by using row and column partitioning and the graph coloring approach, Shahadat A. K. M. Hossain, 1992
Improving bounds for the expected duration in probabilistic activity networks using hypercube multiprocessors, Nils Jacob Berland, 1990