Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The computational complexity of the pooling problem

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

The pooling problem is an extension of the minimum cost flow problem defined on a directed graph with three layers of nodes, where quality constraints are introduced at each terminal node. Flow entering the network at the source nodes has a given quality, at the internal nodes (pools) the entering flow is blended, and then sent to the terminal nodes where all entering flow streams are blended again. The resulting flow quality at the terminals has to satisfy given bounds. The objective is to find a cost-minimizing flow assignment that satisfies network capacities and the terminals’ quality specifications. Recently, it was proved that the pooling problem is NP-hard, and that the hardness persists when the network has a unique pool. In contrast, instances with only one source or only one terminal can be formulated as compact linear programs, and thereby solved in polynomial time. In this work, it is proved that the pooling problem remains NP-hard even if there is only one quality constraint at each terminal. Further, it is proved that the NP-hardness also persists if the number of sources and the number of terminals are no more than two, and it is proved that the problem remains hard if all in-degrees or all out-degrees are at most two. Examples of special cases in which the problem is solvable by linear programming are also given. Finally, some open problems, which need to be addressed in order to identify more closely the borderlines between polynomially solvable and NP-hard variants of the pooling problem, are pointed out.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Adhya, N., Tawarmalani, M., Sahinidis, N.V.: A Lagrangian approach to the pooling problem. Ind. Eng. Chem. Res. 38(5), 1965–1972 (1999)

    Article  Google Scholar 

  2. Alfaki, M., Haugland, D.: Strong formulations for the pooling problem. J. Glob. Optim. 56(3), 897–916 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  3. Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273–286 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  4. Almutairi, H., Elhedhli, S.: A new Lagrangian approach to the pooling problem. J. Glob. Optim. 45(2), 237–257 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Audet, C., Brimberg, J., Hansen, P., Le Digabel, S., Mladenović, N.: Pooling problem: alternate formulations and solution methods. Manag. Sci. 50(6), 761–776 (2004)

    Article  MATH  Google Scholar 

  6. Baker, T.E., Lasdon, L.S.: Successive linear programming at Exxon. Manag. Sci. 31(3), 264–274 (1985)

    Article  MATH  Google Scholar 

  7. Ben-Tal, A., Eiger, G., Gershovitz, V.: Global minimization by reducing the duality gap. Math. Program. 63(1–3), 193–212 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  8. DeWitt, C.W., Lasdon, L.S., Waren, A.D., Brenner, D.A., Melham, S.: OMEGA: an improved gasoline blending system for Texaco. Interfaces 19(1), 85–101 (1989)

    Article  Google Scholar 

  9. Dey, S., Gupte, A.: Analysis of MILP techniques for the pooling problem. Oper. Res. 62(2), 412–427 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  10. Floudas, C.A., Visweswaran, V.: A global optimization algorithm (GOP) for certain classes of nonconvex NLPs: I. Theory Comput. Chem. Eng. 14(12), 1397–1417 (1990)

    Article  Google Scholar 

  11. Foulds, L.R., Haugland, D., Jörnsten, K.: A bilinear approach to the pooling problem. Optimization 24, 165–180 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  12. Galan, B., Grossmann, I.E.: Optimal design of distributed wastewater treatment networks. Ind. Eng. Chem. Res. 37(10), 4036–4048 (1998)

    Article  Google Scholar 

  13. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)

  14. Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237–267 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  15. Gupte, A., Ahmed, S., Dey, S., Cheon, M.: Pooling problems: an overview. In: Furman, K., Song, J. (eds.) Optimization and Analytics in the Oil and Gas Industry, International Series in Operations Research and ManagementScience. Springer, Berlin (2015)

    Google Scholar 

  16. Haverly, C.A.: Studies of the behavior of recursion for the pooling problem. ACM SIGMAP Bull. 25, 19–28 (1978)

    Article  Google Scholar 

  17. Haverly, C.A.: Behavior of recursion models—more studies. ACM SIGMAP Bull. 26, 22–28 (1979)

    Article  Google Scholar 

  18. Kallrath, J.: Solving planning and design problems in the process industry using mixed integer and global optimization. Ann. Oper. Res. 140(1), 339–373 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  19. Kohli, R., Krishnamurti, R., Mirchandani, P.: The minimum satisfiability problem. Discrete Math. 7, 275–283 (1994)

    MathSciNet  MATH  Google Scholar 

  20. McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part 1—Convex underestimating problems. Math. Program. 10(1), 147–175 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  21. Misener, R., Floudas, C.A.: Advances for the pooling problem: modeling, global optimization, and computational studies. Appl. Comput. Math. 8, 3–22 (2009)

    MathSciNet  MATH  Google Scholar 

  22. Misener, R., Floudas, C.A.: Global optimization of large-scale generalized pooling problems: quadratically constrained MINLP models. Ind. Eng. Chem. Res. 49, 5424–5438 (2010)

    Article  Google Scholar 

  23. Misener, R., Thompson, J.P., Floudas, C.A.: APOGEE: global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Comput. Chem. Eng. 35, 876–892 (2011)

    Article  Google Scholar 

  24. Sahinidis, N.V., Tawarmalani, M.: Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints. J. Glob. Optim. 32(2), 259–280 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  25. Visweswaran, V., Floudas, C.A.: Computational results for an efficient implementation of the GOP algorithm and its variants. In: Grossmann, I.E. (ed.) Global Optimization in Chemical Engineering, pp. 111–153. Kluwer, Dordrecht (1996)

    Chapter  Google Scholar 

Download references

Acknowledgments

This article was written while the author was visiting Department of Computer Architecture, University of Málaga, Spain. Invitation and support from Prof. Eligius M.T. Hendrix are gratefully acknowledged.

Author information

Authors and Affiliations

  1. Department of Informatics, University of Bergen, P.O. Box 7803, 5020, Bergen, Norway

    Dag Haugland

Authors
  1. Dag Haugland
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dag Haugland.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Haugland, D. The computational complexity of the pooling problem. J Glob Optim 64, 199–215 (2016). https://doi.org/10.1007/s10898-015-0335-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-015-0335-y

Keywords

Search

Navigation