Photo: Jan Kåre Wilhelmsen	UNIVERSITY OF BERGEN
	Department of Informatics
	Models and Solution Methods for the Pooling Problem
	Dissertation for the PhD-degree

Pipeline transportation of natural gas is largely affected by restrictions regarding gas quality imposed by the market and the actual quality of the gas produced at sources. From the sources, gas flow streams of unequal compositions are mixed in intermediate tanks (pools) and blended again in terminal points. At the pools and the terminals, the quality of the mixture is given as volume-weighted average of the qualities of each mixed gas flow stream. The optimization problem of allocating flow in pipeline transportation networks at minimum cost is referred to as the pooling problem. Such problem is frequently encountered not only in gas transportation planning, but also in the process industries such as petrochemicals.

The pooling problem is a well-studied global optimization problem, which is formulated as a nonconvex (bilinear) problem, and consequently the problem can possibly have many local optima. Despite the strong -hardness of the problem, which is proved formally in this thesis, much progress in solving small to moderate size instances to global optimality has recently been made by use of strong formulations. However, the literature offers few approaches to approximation algorithms and other inexact methods dedicated for large-scale instances. The main contribution of this thesis is the development of strong formulations and efficient solution methods for the pooling problem. In this thesis, we develop a new formulation that proves to be stronger than other formulations based on proportion variables for the standard pooling problem. For the generalized case, we proposes a multi-commodity flow formulation, and prove its strength over formulations from the literature.

Regarding the solution methods, the thesis proposes three solution approaches to tackle the problem. In the first methodology, we discuss solving a simplified version of the standard pooling problem using a solution strategy that based on a sequence of semidefinite programming relaxations. The second approach is based on discretization method in which the pooling problem is approximated by a mixed-integer programming problem. Finally, we give a greedy construction method especially designed to find good feasible solutions for large-scale instances.



The Dissertation is available at: https://bora.uib.no/handle/1956/5847.


Time and date of the trial lecture
May 16, 2012, at 13:15. Given topic: ''Paradoxes in Transportation Networks''
Place: Large Auditorium, 2144, 2nd floor, Datablokken, Høyteknologisenteret, Thormøhlensgate 55.

Time and place for the defense
June 18, 2012, at 10:15, Large Auditorium, 2144, 2nd floor, Datablokken, Høyteknologisenteret, Thormøhlensgate 55.

Members of the evaluation committee

• Associate Professor Leo Liberti, Ècole Polytechnique, France
• Associate Professor Eligius Hendrix, Wageningen University, The Netherlands
• Professor Fredrik Manne, University of Bergen, Norway