A polynomially solvable case of the pooling problem

DOI10.1007/S10898-016-0432-6zbMATH Open1365.90212DBLPjournals/jgo/BolandKR17arXiv1508.03181OpenAlexW1959262530WikidataQ57955263 ScholiaQ57955263MaRDI QIDQ513170FDOQ513170

Authors: Natashia Boland, Thomas Kalinowski, Fabian Rigterink 

Publication date: 3 March 2017

Published in: Journal of Global Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1508.03181

Recommendations

• Pooling problems with polynomial-time algorithms
• The computational complexity of the pooling problem
• Complexity analysis and algorithm design of pooling problem
• Large-scale standard pooling problems with constrained pools and fixed demands
• Pooling problem: alternate formulations and solution methods

zbMATH Keywords

computational complexitypolynomial-time algorithmpooling problem

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
• Global minimization by reducing the duality gap
• A multi-commodity flow formulation for the generalized pooling problem
• Strong formulations for the pooling problem
• Pooling problems with polynomial-time algorithms
• Pooling problem: alternate formulations and solution methods
• Analysis of MILP techniques for the pooling problem
• The computational complexity of the pooling problem
• Partition of Space
• Relaxations and discretizations for the pooling problem
• New multi-commodity flow formulations for the pooling problem

Cited In (9)

• Valid Inequalities for the Pooling Problem with Binary Variables
• Pooling problems with polynomial-time algorithms
• The computational complexity of the pooling problem
• Complexity analysis and algorithm design of pooling problem
• Strong convex nonlinear relaxations of the pooling problem
• Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem
• Analyzing the Pooling Problem
• Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness
• Large-scale standard pooling problems with constrained pools and fixed demands

This page was built for publication: A polynomially solvable case of the pooling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q513170)