Optimization Online


A polynomially solvable case of the pooling problem

Natashia Boland(natashia.boland***at***isye.gatech.edu)
Thomas Kalinowski(thomas.kalinowski***at***newcastle.edu.au)
Fabian Rigterink(fabian.rigterink***at***uon.edu.au)

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.

Keywords: pooling problem; computational complexity

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )


Download: [PDF]

Entry Submitted: 08/13/2015
Entry Accepted: 08/13/2015
Entry Last Modified: 08/13/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society