Tilgjengelege masterprosjekt i optimering

In this project, we want to investigate if deep learning methods can contribute in combinatorial optimization problems in particular if it can find any pattern among good solutions for a pickup and delivery problem and if so, then take advantage of it to lead the search toward even better solutions.

Background: This project challenges your skill in algorithm design and your programming skill! INF273 is highly recommended.

Advisor: Ahmad Hemmati

Develop a Machine Learning based Hyper-heuristic algorithm to solve a pickup and delivery problem. A hyper-heuristic is a heuristics that choose heuristics automatically. Hyper-heuristic seeks to automate the process of selecting, combining, generating or adapting several simpler heuristics to efficiently solve computational search problems [Handbook of Metaheuristics]. There might be multiple heuristics for solving a problem. Heuristics have their own strength and weakness. In this project, we want to use machine-learning techniques to learn the strength and weakness of each heuristic while we are using them in an iterative search for finding high quality solutions and then use them intelligently for the rest of the search. Once a new information is gathered during the search the hyper-heuristic algorithm automatically adjusts the heuristics.

Background: This project challenges your skill in algorithm design and your programming skill! INF273 is highly recommended.

Advisor: Ahmad Hemmati

This project addresses central challenges in climate and energy transition - How do we achieve more efficient transport systems to reduce emissions and improve land use?  The goal of a sustainable logistics system is to improve profitability and reduce environmental impact for long-term performance.  A sustainable logistic need to consider economic, environmental, and social aspects that are essential for a logistics system. In addition, the future state of transportation systems in smart cities requires taking advantage of multimodal transportation that includes autonomous electric cars, boats, trains, Robots, and drones.     In  this  project,  we  aim  at  developing  optimization models and artificial intelligence (AI) solutions  for  the  problem  of  integrated multimodal transport planning, taking into account social, environmental, geographical and economical constraints. Transport planning is a complex combinatorial optimization problem and social, environmental and economic factors increases the complexity. This cross-disciplinary project is well positioned to solve this complex problem by combining expertise in optimization, AI, Logistics, and social science within urban development, governance and public perceptions.This project can be divided into three different master projects.

Background: This project challenges your skill in algorithm design and your programming skill! INF273 is highly recommended.

Advisor: Ahmad Hemmati

For details please see the project description!

Industry partner: Schlumberger

Advisor: Jan Rückmann

Maritime transportation is the obvious choice for heavy industrial activities where large volumes are transported over long distances. Norway is currently among the world's top 10 shipping nations in terms of tonnage, the number of vessels and the value of the fleet. Operational efficiency of maritime transportation can have a huge effect on consumers by reducing final product costs. In this project, we address the ship routing and scheduling problem, which is one of the main problems in maritime transportation. In this problem, a shipping company has a set of contracted cargoes that it is committed to carry and there are also some spot cargoes available in the market. Each cargo in the given planning period must be picked up at its port of loading, transported and then delivered to its corresponding discharging port. There are time windows given, within which the loading of the cargoes must start, and there may also exist time windows for discharging. The shipping company can decide to serve some of the spot cargoes if they find it profitable. This is a NP-hard problem and we are going to develop a powerful heuristic to solve the real size instances of the problem!

Background: This project challenges your skill in algorithm design and your programming skill! INF273 is highly recommended.

Advisor: Ahmad Hemmati

Among various problems considered in supply chain logistics, pickup and delivery problem with time windows is one of the most practical one that has received a lot of attentions in the operation research community. Here we consider a shipping company, which operates a heterogeneous fleet of vehicles. At a given point in time we consider a static and deterministic planning problem, consisting of determining how the fleet of vehicles should service a set of given requests. The vehicles may be different in capacity, speed and cost, and compatibility for carrying certain request. If a request is assigned to a vehicle, the vehicle must pickup the request in its corresponding origin point (pickup node) and later deliver the request in its destination point (delivery node). All pickups and deliveries operations must be performed within a time interval that is specific to that operation for a given request. Pickup and delivery problem has many applications such as in postal service and food industry. In this project, we are going to solve a very practical application of this problem which has more realistic assumptions than the original described version.

Background: This project challenges your problem solving and programming skill as well as your skill in algorithm design! INF273 is highly recommended.

Advisor: Ahmad Hemmati

Maritime transportation is the obvious choice for heavy industrial activities where large volumes are transported over long distances. Norway is currently among the world's top 10 shipping nations in terms of tonnage, the number of vessels and the value of the fleet. Operational efficiency of maritime transportation can have a huge effect on consumers by reducing final product costs. In this project, we address the multi-productmaritime inventory routing problem where each product can be produced and consumed in any number of ports. During the planning horizon the level of each inventory of each product at each port must lie within fixed lower and upper limits at all times. There are lower and upper limits on the loaded and unloaded quantities. These operations generate fixed and variable costs. The multi-product maritime inventory routing problem consists of designing routes and schedules for the fleet in order to minimize the transportation and port costs, and to determine the quantities handled at each port call without exceeding the storage limits. We intend to mathematically formulate the problem and possibly find the upper and lower bounds. Since it is a NP-hard problem, to solve the real size instances of the problem, we are going to develop a powerful heuristic!

Background: This project challenges your skill in Mathematical formulation and your programming skill! INF273 is highly recommended.

Advisor: Ahmad Hemmati

In a covering location problem, we seek location of a number of facilities on a network in such a way that the covered population is maximized. A population is covered if at least one facility is located within a predefined distance of it. This predefined distance is often called coverage radius. The choice of this distance has a vital role and affects the optimal solution of the problem to a great extent. Covering location problem is of paramount importance in practice to locate many service facilities such as schools, parks, hospitals and emergency units. In some practical cases, the population is moving during the planning horizon. In this project, we are going to develop a heuristic for the problem assuming the moving population.

Background: This project challenges your skill in algorithm design and your programming skill! INF273 is highly recommended.

Advisor: Ahmad Hemmati

Adaptive large neighbourhood search is a popular and widely used algorithm in the literature in solving combinatorial problems and in particular routing problems. In this project, we are going to investigate the role of randomized components in this algorithm and provide deterministic alternatives that work as good as the original one, or even better!

Background: This project challenges your skill in algorithm design and your analytical and logical thinking! INF273 is highly recommended.

Advisor: Ahmad Hemmati

A location-routing problem may be defined as an extension to a multi depot vehicle routing problem in which there is a need to determine the optimal number and location of depots simultaneously with finding distribution routes. LRP is an NP-hard problem, as it encompasses two NP-hard problems (facility location and vehicle routing). Moreover, it is generally accepted that solving the two sub-problems separately often leads to sub-optimal solutions. LRP has many real-life applications such as in food and drink distribution, postal service, blood bank location, newspaper distribution, waste collection, and medical evacuation. In this project, we are going to solve a practical application of this problem which has more realistic assumptions than the original described version.

Background: This project challenges your problem solving and programming skill as well as your skill in algorithm design! INF273 is highly recommended.

Advisor: Ahmad Hemmati

The Newton- Raphson method is the most used method for solving nonlinear equations (or  finding a root of) f(x)=0. It is an iterative method and in every iteration it uses f(x) and f'(x). Halley's method uses f(x), f'(x) and f''(x) at every iteration. In a textbook on iterative methods the author claims that Halley's method is the most rediscovered method. The purpose of this project is to explore the different ways to derive the method and follow the historical thread  and to explore the algorithmic consequences of the different derivations of Halley's method. For more information on the project contact the supervisor professor Trond Steihaug.

Advisor: Trond Steihaug

When we say that one algorithm is more efficient than another algorithm in optimization, we often compare number of arithmetic operations. However, the amount of memory and memory access is often as important. Simple algorithms with input size n require O(n^3) arithmetic operations, and a memory usage of O(n^2), but behave as if the memory access were O(n^3), due to misses in the cache of the computer. In this project you will test different data structures with different memory access. The project requires extensive programming. For more information on the project contact the supervisor professor Trond Steihaug.

Advisor: Trond Steihaug

This topic covers the application of several solution methods for nonlinear optimization problems. Nonlinear Optimization (or Programming) models can be used for the modelling, description and solution of real-life application from a huge variety of areas; among them are finance, economics, production planning, trajectory calculation and others. In dependence on the chosen application and the recommended solution method the corresponding master thesis project might include modelling and numerical solution aspects.

Advisor: Jan Rückmann

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

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.

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.

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.

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.

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.

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.

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.

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:

• Heuristics
• 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.