A polynomially solvable case of the pooling problem

详细信息    查看全文

• 作者：Natashia Boland ; Thomas Kalinowski ; Fabian Rigterink
• 关键词：Pooling problem ; Computational complexity ; Polynomial ; time algorithm
• 刊名：Journal of Global Optimization
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：67
• 期：3
• 页码：621-630
• 全文大小：
• 刊物类别：Business and Economics
• 刊物主题：Optimization; Operation Research/Decision Theory; Real Functions; Computer Science, general;
• 出版者：Springer US
• ISSN：1573-2916
• 卷排序：67

文摘

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.