Models and Solution Methods for the Pooling Problem
MetadataShow full item record
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 NP-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.
Paper A: Alfaki, M. and Haugland, D. (2012). Strong formulations for the pooling problem. In: Journal of Global Optimization. Full text not available in BORA due to publisher restrictions. The article is available at: http://dx.doi.org/10.1007/s10898-012-9875-6Paper B: Alfaki, M. and Haugland, D. (2012). A multi-commodity flow formulation for the generalized pooling problem. In: Journal of Global Optimization. Full text not available in BORA due to publisher restrictions. The article is available at: http://dx.doi.org/10.1007/s10898-012-9890-7Paper C: Frimannslund, L., El Ghami, M., Alfaki, M. and Haugland, D. (2010). Solving the pooling problem with LMI relaxations. A short version is published in: S. Cafieri, B. G.-Tóth, E. Hendrix, L. Liberti and F. Messine (Eds.), Proceedings of the Toulouse Global Optimization Workshop (pp. 51–54). The article is available at: http://hdl.handle.net/1956/5853Paper D: Alfaki, M. and Haugland, D. (2011). Comparison of discrete and continuous models for the pooling problem. In: A. Caprara and S. Kontogiannis (Eds.), 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (Vol. 20, pp. 112–121). OpenAccess Series in Informatics (OASIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. The article is available at: http://hdl.handle.net/1956/5848Paper E: Alfaki, M. and Haugland, D. (2011). Computing feasible solutions to the pooling problem. Submitted to: Annals of Operations Research, 2011. Full text not available in BORA.