The computational complexity of the pooling problem

详细信息    查看全文

• 作者：Dag Haugland
• 关键词：Pooling problem ; Network flow ; Computational complexity ; Polynomial reduction
• 刊名：Journal of Global Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：64
• 期：2
• 页码：199-215
• 全文大小：733 KB
• 参考文献：1.Adhya, N., Tawarmalani, M., Sahinidis, N.V.: A Lagrangian approach to the pooling problem. Ind. Eng. Chem. Res. 38(5), 1965–1972 (1999)CrossRef
  2.Alfaki, M., Haugland, D.: Strong formulations for the pooling problem. J. Glob. Optim. 56(3), 897–916 (2013)CrossRef MathSciNet
  3.Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273–286 (1983)CrossRef MathSciNet
  4.Almutairi, H., Elhedhli, S.: A new Lagrangian approach to the pooling problem. J. Glob. Optim. 45(2), 237–257 (2009)CrossRef MathSciNet
  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)CrossRef
  6.Baker, T.E., Lasdon, L.S.: Successive linear programming at Exxon. Manag. Sci. 31(3), 264–274 (1985)CrossRef
  7.Ben-Tal, A., Eiger, G., Gershovitz, V.: Global minimization by reducing the duality gap. Math. Program. 63(1–3), 193–212 (1994)CrossRef MathSciNet
  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)CrossRef
  9.Dey, S., Gupte, A.: Analysis of MILP techniques for the pooling problem. Oper. Res. 62(2), 412–427 (2015)CrossRef MathSciNet
  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)CrossRef
  11.Foulds, L.R., Haugland, D., Jörnsten, K.: A bilinear approach to the pooling problem. Optimization 24, 165–180 (1992)CrossRef MathSciNet
  12.Galan, B., Grossmann, I.E.: Optimal design of distributed wastewater treatment networks. Ind. Eng. Chem. Res. 37(10), 4036–4048 (1998)CrossRef
  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)CrossRef MathSciNet
  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)
  16.Haverly, C.A.: Studies of the behavior of recursion for the pooling problem. ACM SIGMAP Bull. 25, 19–28 (1978)CrossRef
  17.Haverly, C.A.: Behavior of recursion models—more studies. ACM SIGMAP Bull. 26, 22–28 (1979)CrossRef
  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)CrossRef MathSciNet
  19.Kohli, R., Krishnamurti, R., Mirchandani, P.: The minimum satisfiability problem. Discrete Math. 7, 275–283 (1994)MathSciNet
  20.McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part 1—Convex underestimating problems. Math. Program. 10(1), 147–175 (1976)CrossRef MathSciNet
  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
  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)CrossRef
  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)CrossRef
  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)CrossRef MathSciNet
  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)CrossRef
  
• 作者单位：Dag Haugland (1)
  
  1. Department of Informatics, University of Bergen, P.O. Box 7803, 5020, Bergen, Norway
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Computer Science, general
  Real Functions
  Optimization
  
• 出版者：Springer Netherlands
• ISSN：1573-2916

文摘

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. Keywords Pooling problem Network flow Computational complexity Polynomial reduction