Pågående masterprosjekt

Rask løsning av Quadratic Programming (QP) Problem

Goodtech og MathConsult har utviklet et verktøy for å beregne leveransepåliteligheten i et masket nettverk, der hver gren har en feilfrekvens. Denne metoden baserer seg på pålitelighetsteori til å plukke ut aktuelle feilsituasjoner for videre analyse, og optimaliseringsteori for å beregne optimal leveranse igjennom nettverket ved hver enkelte feilsituasjoner. Optimaliseringsproblemene blir formulert som QP-problem.

På grunna av at mulige antall feilsituasjoner stiger svært fort i forhold til størrelsen på nettet, så er programmet avhengig av hvert enkelte feilsituasjon blir analysert svært raskt. Igjennom en studie av tilgjengelige QP-løseres, har utviklergruppa komt frem til at CPLEX er den mest effektive løseren for problemstillingen. Men siden CLPEX er dyr og ikke spesialisert for den gjeldende problemstillingen, er Goodtech interessert i å se på muligheten for å få utviklet en egen QP-løser. Håpet er at en spesialtilpasset løser vil bli enda raskere enn CPLEX.

Studenten skal utvikle en QP-løser for effektiv løsing av problemer med følgende karakteristikk:

•                    Størrelsesorden 100 – 2000 variabler, men med mulighet for å redusere problemstørrelsen igjennom variabeleliminasjon.

•                    Glisne matriser.

•                    Positiv semidefinitt kvadratisk ledd i objektfunksjonen.

•                    QP-problemet skal løses mange ganger (tusenvis) med små variasjoner i beskrankningene.

Goodtech legger ikke føringer på hvilke metoder som skal brukes, men kan stille med erfaring fra tidligere studier av QP-løsere. Goodtech kan også stille med beskrivelse av problemstilling, inngangsdata til testing, veileder i bedrift og arbeidsplass.

Veileder: Dag Haugland.

Student: Andreas Halle

Enrolled semester: Fall 2011

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