CORAL Seminar: Dag Haugland, Department of Informatics, University of Bergen, Norway

Title: The Pooling Problem - Applications, Complexity and Solution Methods

2014.02.24 | Bodil Westermann Krog

Date Tue 03 Jun
Time 14:00 15:00
Location Fuglesangs Allé 4, 8210 Aarhus V, building 2628(M), room 323

Speaker: Dag Haugland, Department of Informatics, University of Bergen, Norway

Title: The Pooling Problem - Applications, Complexity and Solution Methods

Abstract: Since the very first computer programs for linear programming (LP) were commercialized, the oil refining industry has been a major beneficiary. Relations between input and output are for most refinery processes described reasonably accurately by linear equations, making LP an efficient and effective tool for planning the production. However, practical experience soon told that certain, apparently linear, processes were difficult to handle by LP.
    Blending (pooling) of product streams with unequal contamination levels, such as CO2-contents, is straightforwardly modeled by defining the output contamination as a weighted average of the input contamination levels. For instance, if one unit of flow with 1% CO2 is blended with three units of 2% CO2, the output flow will have 1.75% CO2. Despite this simplicity, quality updates in blending processes have always challenged LP-model builders in the petrochemical industry.
    To study the model implications of blending operations, we consider the pooling problem, which is a network flow problem defined on a directed graph consisting of three sets of nodes: Sources, pools and terminals. Flow streams enter the network at the sources, from where they are sent to the pools to be blended, and finally they continue to the terminals. The qualities of the flow leaving the sources are given by source-specific input parameters. Likewise, the terminals have parameters specifying the quality requirements. Pools and terminals are considered as blending processes, where resulting qualities are defined as in the CO2 example. The problem is to assign flow to the network arcs in such a way that flow conservation and capacity constraints are satisfied, such that the quality requirements at the terminals are met, and such that the total costs are minimized.
    In this work, we demonstrate that the pooling problem is NP-hard, which implies that it is unlikely that an LP-formulation for the problem exists. We give examples of simple network configurations where hardness persists, explaining why blending processes are so difficult to fit to the LP-framework. Further, we suggest how the pooling problem can be formulated in order to be solvable by a global optimization algorithm, and finally we discuss some possibly inexact methods targeted to large scale instances.

Organizer: Sanne Wøhlk

 

CORAL seminars