The computational complexity of the pooling problem

DOI10.1007/S10898-015-0335-YMaRDI QIDQ5964238zbMATH OpenOpenAlexFDO

Authors Dag Haugland

Publication date 29 February 2016

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

Full work available at URL https://doi.org/10.1007/s10898-015-0335-y

zbMATH Keywords

computational complexitynetwork flowpolynomial reductionpooling problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Pooling problems with polynomial-time algorithms
• Complexity analysis and algorithm design of pooling problem
• A polynomially solvable case of the pooling problem
• A multi-commodity flow formulation for the generalized pooling problem
• A cost minimization heuristic for the pooling problem

Cites work

• A bilinear approach to the pooling problem†
• A new Lagrangean approach to the pooling problem
• Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints
• Advances for the pooling problem: modeling, global optimization, and computational studies (Survey)
• Analysis of MILP techniques for the pooling problem
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Global minimization by reducing the duality gap
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1054665 (Why is no real title available?)
• Jointly Constrained Biconvex Programming
• Pooling problem: alternate formulations and solution methods
• Solving planning and design problems in the process industry using mixed integer and global optimization
• Some simplified NP-complete graph problems
• Strong formulations for the pooling problem
• Successive Linear Programming at Exxon
• The Minimum Satisfiability Problem

Cited in

(15)

• A numerical evaluation of the bounded degree sum-of-squares hierarchy of Lasserre, Toh, and Yang on the pooling problem
• Complexity analysis and algorithm design of pooling problem
• Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness
• Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem
• Valid Inequalities for the Pooling Problem with Binary Variables
• Pooling problems with polynomial-time algorithms
• Some results on pooling
• Analyzing the Pooling Problem
• A cost minimization heuristic for the pooling problem
• Strong convex nonlinear relaxations of the pooling problem
• A polynomially solvable case of the pooling problem
• On the effectiveness of sequential linear programming for the pooling problem
• Tightening discretization-based MILP models for the pooling problem using upper bounds on bilinear terms
• Minimun overlap problem on finite groups
• Improved rank-one-based relaxations and bound tightening techniques for the pooling problem

Describes a project that uses

Uses Software

• APOGEE

This page was built for publication: The computational complexity of the pooling problem

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