← Back to papers

A polynomially solvable case of the pooling problem

Natashia Boland, Thomas Kalinowski, Fabian Rigterink

Journal of Global Optimization · 67(3):621–630 · 2017 · DOI: 10.1007/s10898-016-0432-6

Journal of Global Optimization coverA polynomially solvable case of the pooling problem first page
Pooling problemComputational complexityPolynomial-time algorithm

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.