Show simple item record

dc.contributor.authorAlfaki, Mohammedeng
dc.date.accessioned2012-06-14T11:39:51Z
dc.date.available2012-06-14T11:39:51Z
dc.date.issued2012-06-18eng
dc.identifier.isbn978-82-308-2051-3 (print version)en_US
dc.identifier.urihttps://hdl.handle.net/1956/5847
dc.description.abstractPipeline 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.en_US
dc.language.isoengeng
dc.publisherThe University of Bergenen_US
dc.relation.haspartPaper 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: <a href="http://dx.doi.org/10.1007/s10898-012-9875-6" target="blank">http://dx.doi.org/10.1007/s10898-012-9875-6</a>en_US
dc.relation.haspartPaper 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: <a href="http://dx.doi.org/10.1007/s10898-012-9890-7" target="blank">http://dx.doi.org/10.1007/s10898-012-9890-7</a>en_US
dc.relation.haspartPaper 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: <a href="http://hdl.handle.net/1956/5853" target="blank">http://hdl.handle.net/1956/5853</a>en_US
dc.relation.haspartPaper 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: <a href="http://hdl.handle.net/1956/5848" target="blank">http://hdl.handle.net/1956/5848</a>en_US
dc.relation.haspartPaper 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.en_US
dc.subjectGlobal Optimizationeng
dc.subjectPooling Problemeng
dc.subjectComputational complexityeng
dc.subjectBilinear Programmingeng
dc.subjectLinear matrix inequalityeng
dc.subjectHeuristic methodseng
dc.subjectIndustrial Optimizationeng
dc.titleModels and Solution Methods for the Pooling Problemen_US
dc.typeDoctoral thesis
dc.rights.holderCopyright the author. All rights reserveden_US
dc.subject.nsiVDP::Mathematics and natural science: 400::Information and communication science: 420en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record