License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2011.112
URN: urn:nbn:de:0030-drops-32719
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3271/
Go to the corresponding OASIcs Volume Portal


Alfaki, Mohammed ; Haugland, Dag

Comparison of discrete and continuous models for the pooling problem

pdf-format:
11.pdf (0.4 MB)


Abstract

The pooling problem is an important global optimization problem which is encountered in many industrial settings. It is traditionally modeled as a bilinear, nonconvex optimization problem, and solved by branch-and-bound algorithms where the subproblems are convex. In some industrial applications, for instance in pipeline transportation of natural gas, a different modeling approach is often made. Rather than defining it as a bilinear problem, the range of qualities is discretized, and the complicating constraints are replaced by linear ones involving integer variables. Consequently, the pooling problem is approximated by a mixed-integer programming problem. With a coarse discretization, this approach represents a saving in computational effort, but may also lead to less accurate modeling. Justified guidelines for choosing between a bilinear and a discrete model seem to be scarce in the pooling problem literature. In the present work, we study discretized versions of models that have been proved to work well when formulated as bilinear programs. Through extensive numerical experiments, we compare the discrete models to their continuous ancestors. In particular, we study how the level of discretization must be chosen if a discrete model is going to be competitive in both running time and accuracy.

BibTeX - Entry

@InProceedings{alfaki_et_al:OASIcs:2011:3271,
  author =	{Mohammed Alfaki and Dag Haugland},
  title =	{{Comparison of discrete and continuous models for the pooling problem}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{112--121},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Alberto Caprara and Spyros Kontogiannis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3271},
  URN =		{urn:nbn:de:0030-drops-32719},
  doi =		{10.4230/OASIcs.ATMOS.2011.112},
  annote =	{Keywords: Global Optimization,  Industrial Optimization,  Graphs and Networks, Pooling problem}
}

Keywords: Global Optimization, Industrial Optimization, Graphs and Networks, Pooling problem
Collection: 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue Date: 2011
Date of publication: 19.09.2011


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI