Fast methods to solve 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 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.Master i InformatikkMAMN-INFINF39