Staff Publications

Staff Publications

  • external user (warningwarning)
  • Log in as
  • language uk
  • About

    'Staff publications' is the digital repository of Wageningen University & Research

    'Staff publications' contains references to publications authored by Wageningen University staff from 1976 onward.

    Publications authored by the staff of the Research Institutes are available from 1995 onwards.

    Full text documents are added when available. The database is updated daily and currently holds about 240,000 items, of which 72,000 in open access.

    We have a manual that explains all the features 

Record number 504248
Title Pooling Problems with Polynomial-Time Algorithms
Author(s) Haugland, Dag; Hendrix, Eligius M.T.
Source Journal of Optimization Theory and Applications (2016). - ISSN 0022-3239 - p. 591 - 615.
Department(s) Operations Research and Logistics
Publication type Refereed Article in a scientific journal
Publication year 2016
Keyword(s) Complexity - Global optimization - Polynomial-time algorithm - Pooling problem

The computational challenge offered by many traditional network flow models is modest, and large-scale instances can be solved fast. When the composition of the flow is part of the model, the required computation time may increase substantially. This is in particular true for the pooling problem, where the relative content of certain flow components is restricted. Flow entering the network at the source nodes has a given composition, whereas the composition in other nodes is determined by the composition of entering flows. At the network terminals, the flow composition is subject to restrictions referred to as quality constraints. The pooling problem is known to be strongly NP-hard, even if the network has only one pool, but is solvable in polynomial time if also the number of terminals or the number of quality parameters (flow components) is bounded. The problem is also NP-hard if there are only two sources and terminals and only one quality parameter. Two related questions have been left open in the literature so far. For the single-pool version, it has not been known whether the problem is solvable in polynomial time if the number of sources is bounded. For the version with a single quality parameter and two sources and terminals, the question whether a pseudo-polynomial algorithm exists has been open. This paper gives positive answers to both questions.

There are no comments yet. You can post the first one!
Post a comment
Please log in to use this service. Login as Wageningen University & Research user or guest user in upper right hand corner of this page.