Ongoing master theses

Ongoing theses

(Near) Optimal Cable Layout in Offshore Windfarms

For offshore windfarms 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.

Advisor: Joanna Bauer 

Student: Thomas Amland

Enrolled semester: Spring 2012

 

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 CO2, 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 CO2-content becomes a weighted average of the relative CO2-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.

Student: Anisha Kejriwal

Enrolled semester: Fall 2012

 

The tracking error problem with a cardinality constraint on the number of assets

When a cardinality constraint restricting the number of assets is introduced in a portfolio, the problem of optimizing the selection of assets becomes NP-hard. Heuristics and possible solutions have been suggested. Woodside, Lucas & Beasley (2011) presents a heuristic algorithm for the cardinality constrained efficient frontier where they consider the mean variance model of Markowitz including the restrictions of buy-in thresholds and cardinality constraints. Coleman (2006) presents a graduated non-convexity method to minimize portfolio tracking error with the total number of assets no greater than a specified integer. These are two of the not so few proposals that have been suggested to solving this problem.

There exist different portfolio management strategies to choose from while making investment decisions. For each of these strategies, managers are faced with a myriad of factors to consider. For the active and passive managers, the focus is on maximizing the returns and for the other is minimizing the risk respectively. Several decisions on investments are made from predictions or calculations from historical data in the hope that they aid in choice of a good portfolio.

Passive fund managers focus on index tracking and they are faced with the challenge of the tracking error (TE). TE is the difference between the manager’s portfolio and the benchmark. Several factors contribute to the TE and these include trading costs, differences in the composition of the portfolio to mention but a few. To minimize the TE involves selecting a portfolio that will track the index at a low cost. Replication increases the TE for it increases the trading costs. It is therefore of high significance to select a portfolio that will result to a minimum TE.

While examining other approaches related to this area of research, using combinatorial optimization techniques and quadratic programming, I will attempt to solve the TE problem with a cardinality constraint on the number of assets to be selected for the portfolio. NP-hardness means that exact solutions are computationally infeasible with increase in the amount of data for implementation thus only the inexact methods are practical. This thesis will seek to balance between computational time and the quality of the results during implementation.

Advisor: Dag Haugland

Student: Purity Mutunge

Enrolled semester: Spring 2012

 

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.

Student: Vithya Ganeshan

Enrolled semester: Spring 2014

 

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.

Student: Valery Tchouatchoua

Enrolled semester: Fall 2013

 

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