Master theses in Optimization

Ledige masteroppgaverer

Kodetransformasjoner og optimering

Se følgende YouTube for introduksjon http://www.youtube.com/watch?v=a9P5Ql-A7pM

"Source to source" kildetransformasjoner tar som input et datamaskinprogram for beregning av en funksjon av flere variabler og generere ny kildekode for beregning av funksjonen og den deriverte. I tillegg til funksjonen må brukeren fortelle hvilke variabler som skal betraktes som uavhengige og avhengige (og dermed ta den deriverteav de avhengige mhp de uavhengige) . Eksempler på slike programmer for kodetransformasjoner er ADG, ADIFOR, TAPENADE, ADOL-C avhengig av hvilket språk som benyttes. (Se http://www.autodiff.org/ for en introduksjon til automatisk derivasjon og programvare)

I prosjektet skal vi anvende prosessen rekursivt: kildetransformasjon av den transformerte koden.  Rent symbolsk skulle vi dermed kunne få alle høyere deriverte. Vi skal studere effekten av datastrukturer på effektiviteten av kildetransformasjonen.

Veileder: Trond Steihaug
Bakgrunn: Du bør ha matematikk nok til å vite hva Jacobi- og Hesse-matrisen er.

(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.

The exact content of the project(s) will depend on the interests and qualifications of the candidate(s). Projects with main focus on computer implementations, or on theoretical studies are both possible and welcome :)

Advisor: Joanna Bauer

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.

Spesialsydde algoritmer for fargelegging av grafer

Det å gjenskape en matrise fra matrise-vektor produkter hvor vi kjenner hvor null-elementene befinner seg er et viktig problem. Det kan vises at dette problemet er spesialtilfelle av fargelegging av en graf.

Det er flere mulige problemstillinger knyttet til denne oppgaven.

• En problemstilling er å se på formuleringen av fargeleggingsproblemet og benytte 'symmetri' egenskaper til å redusere løsningsmengden. Et eksempel på en slik symmetri er at vi kan bytte om fargene ved fargelegging av en graf.
• En annen problemstilling er å se på matriser med spesielle egenskaper. For en struktur kan vi f.eks. få et 'star coloring' problem.

I oppgaven skal vi formulere fargeleggingsproblemet som et heltallsoptimeringsproblem. Her er mer info om CPR og sammenhengen med fargelegging av en graf.

Nødvendig bakgrunn: Av optimering forutsettes kombinatorisk og (noe) ikke-lineær optimering tilegnet i løpet av studiet. Bakgrunn for ikkelineære problemer kan leses parallelt.
Veileder: Trond Steihaug.

Fleksible datastrukturer i Java for matrise- og tensorberegninger

Vi har utvikler flere datastrukturer for glisne matriser som bruker array av array for å lage både effektive og fleksible datastrukturer. Oppgaven går ut på å implementere forskjellige algoritmer med disse datastrukturene og teste effektiviten. For informasjon om datastrukturen JSA se publikasjoner.

Nødvendig bakgrunn: Av optimering forutsettes kun INF170/INF270 eller tilsvarende kunnskap. Nødvendig bakgrunn for ikkelineære problemer kan leses parallelt. Det er nødvendig med noe numerisk lineær algebra.
Veileder: 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.

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.