A polynomially solvable case of the pooling problem

DOI10.1007/S10898-016-0432-6MaRDI QIDQ513170zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Natashia Boland, Thomas Kalinowski, Fabian Rigterink

Publication date 3 March 2017

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

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

zbMATH Keywords

computational complexitypolynomial-time algorithmpooling problem

Mathematics Subject Classification ID

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

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.

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

Cites work

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