## Fast methods to solve the pooling problem

##### Type

Master thesis###### Not peer reviewed

##### View/Open

##### Date

2014-05-31##### Author

##### Metadata

Show full item record##### Abstract

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 in 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.
This thesis focuses on the development of inexact or heuristic
techniques for the pooling problem.
The aim of these techniques is to find good feasible solutions for
large pooling problem instances at a reasonable computation
cost, and
the methods do not guarantee global optimality.
In order to achieve this, three approaches are discussed in this
thesis.
First, we propose an improvement heuristic which iteratively
reduces the total cost.
%new line
Since the quality of the solutions provided by the improvement
method depends upon good initial solutions,
we propose construction heuristic methods that give good
feasible solutions for the pooling problem.
The methods construct a sequence of sub-graphs, each of which
contains a single terminal, and an associated linear program for
optimizing the flow to the terminal.
The optimal solution to each linear program serves as a feasible
augmentation of total flow accumulated so far.
Finally, we combine both the above mentioned methods, such
that the solution given by the construction heuristic is used as
the starting solution by the improvement method.
Computational experiments indicate that all the heuristic
methods proposed in this thesis are faster compared to the
heuristics that were proposed earlier.
Since the exact solutions are not known in large instances, the
solutions given by the heuristic methods are compared to lower
bounds on the optimal objective function value.
In this thesis, we also propose a constraint generation algorithm,
that aims to compute lower bounds on the minimum cost fast.

##### Publisher

The University of Bergen##### Collections

Copyright the author. All rights reserved