A polynomially solvable case of the pooling problem

Author(s)
Boland, Natashia
Kalinowski, Thomas
Rigterink, Fabian
Publication Date
2017-03
Abstract
Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs can be solved in polynomial time by solving a polynomial number of linear programs of polynomial size. We also give an overview of known complexity results and remaining open problems to further characterize the border between (strongly) NP-hard and polynomially solvable cases of the pooling problem.
Citation
Journal of Global Optimization, 67(3), p. 621-630
ISSN
1573-2916
0925-5001
Link
https://hdl.handle.net/1959.11/26777
Publisher
Springer New York LLC
Title
A polynomially solvable case of the pooling problem
Type of document
Journal Article
Entity Type
Publication

Files:

NameSizeformatDescriptionLink