Pooling Problems with Polynomial-Time Algorithms

Dag Haugland, Eligius M.T. Hendrix

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

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.

LanguageEnglish
Pages591-615
JournalJournal of Optimization Theory and Applications
DOIs
Publication statusPublished - 2016

Fingerprint

Pooling
Polynomial-time Algorithm
Polynomials
Chemical analysis
Polynomial time
NP-complete problem
Network Flow
Polynomial Algorithm
Vertex of a graph
Polynomial-time algorithm
Restriction
Model
Quality parameters

Keywords

  • Complexity
  • Global optimization
  • Polynomial-time algorithm
  • Pooling problem

Cite this

@article{fed5d3e044c14bc0bfdb1ea4cd2d3ff4,
title = "Pooling Problems with Polynomial-Time Algorithms",
abstract = "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.",
keywords = "Complexity, Global optimization, Polynomial-time algorithm, Pooling problem",
author = "Dag Haugland and Hendrix, {Eligius M.T.}",
year = "2016",
doi = "10.1007/s10957-016-0890-5",
language = "English",
pages = "591--615",
journal = "Journal of Optimization Theory and Applications",
issn = "0022-3239",
publisher = "Plenum Press",

}

Pooling Problems with Polynomial-Time Algorithms. / Haugland, Dag; Hendrix, Eligius M.T.

In: Journal of Optimization Theory and Applications, 2016, p. 591-615.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Pooling Problems with Polynomial-Time Algorithms

AU - Haugland, Dag

AU - Hendrix, Eligius M.T.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Complexity

KW - Global optimization

KW - Polynomial-time algorithm

KW - Pooling problem

U2 - 10.1007/s10957-016-0890-5

DO - 10.1007/s10957-016-0890-5

M3 - Article

SP - 591

EP - 615

JO - Journal of Optimization Theory and Applications

T2 - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

SN - 0022-3239

ER -