×

zbMATH — the first resource for mathematics

Analysis of MILP techniques for the pooling problem. (English) Zbl 1327.90351
Summary: The \(pq\)-relaxation for the pooling problem can be constructed by applying McCormick envelopes for each of the bilinear terms appearing in the so-called \(pq\)-formulation of the pooling problem. This relaxation can be strengthened by using piecewise-linear functions that over- and under-estimate each bilinear term. Although there is a significant amount of empirical evidence to show that such piecewise-linear relaxations, which can be written as mixed-integer linear programs (MILPs), yield good bounds for the pooling problem, to the best of our knowledge, no formal result regarding the quality of these relaxations is known. In this paper, we prove that the ratio of the upper bound obtained by solving piecewise-linear relaxations (objective function is maximization) to the optimal objective function value of the pooling problem is at most \(n\), where \(n\) is the number of output nodes. Furthermore for any \( \epsilon > 0 \) and for any piecewise-linear relaxation, there exists an instance where the ratio of the relaxation value to the optimal value is at least \( n - \epsilon\). This analysis naturally yields a polynomial-time \(n\)-approximation algorithm for the pooling problem. We also show that if there exists a polynomial-time approximation algorithm for the pooling problem with guarantee better than \( n^{1-\epsilon}\) for any \( \epsilon > 0 \), then NP-complete problems have randomized polynomial-time algorithms. Finally, motivated by the approximation algorithm, we design a heuristic that involves solving an MILP-based restriction of the pooling problem. This heuristic is guaranteed to provide solutions within a factor of \(n\). On large-scale test instances and in significantly lesser time, this heuristic provides solutions that are often orders of magnitude better than those given by commercial local and global optimization solvers.

MSC:
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
Software:
APOGEE; XPRESS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alfaki M, Haugland D (2011) Comparison of discrete and continuous models for the pooling problem. Caprara A, Kontogiannis S, eds. 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optim., Systems (ATMOS), OpenAccess Series in Informatics (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 112-121. · Zbl 1247.90216
[2] Alfaki M, Haugland D (2014) A cost minimization heuristic for the pooling problem. Ann. Oper. Res. 222(1):73-87.CrossRef · Zbl 1303.90110
[3] Alfaki M, Haugland D (2013) Strong formulations for the pooling problem. J. Global Optim. 56(3):897-916.CrossRef · Zbl 1272.90054
[4] Audet C, Brimberg J, Hansen P, Le Digabel S, Mladenović N (2004) Pooling problem: Alternate formulations and solution methods. Management Sci. 50(6):761-776.Abstract · Zbl 1232.90349
[5] Baker TE, Lasdon LS (1985) Successive linear programming at Exxon. Management Sci. 31(3):264-274.Abstract · Zbl 0608.90090
[6] Ben-Tal A, Eiger G, Gershovitz V (1994) Global minimization by reducing the duality gap. Math. Programming 63(1):193-212.CrossRef · Zbl 0807.90101
[7] D’Ambrosio C, Linderoth J, Luedtke J (2011) Valid inequalities for the pooling problem with binary variables. Günlük O, Woeginger G, eds. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 6655 (Springer, Berlin, Heidelberg), 117-129.CrossRef · Zbl 1339.90238
[8] Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91:201-213.CrossRef · Zbl 1049.90004
[9] FICO (2013) FICO Xpress Optimization Suite 7.5. http://www.fico.com/xpress.
[10] Gounaris CE, Misener R, Floudas CA (2009) Computational comparison of piecewise-linear relaxations for pooling problems. Indust. Engrg. Chemistry Res. 48(12):5742-5766.CrossRef
[11] Gupte A, Ahmed S, Cheon MS, Dey S (2013) Relaxations and discretizations for the pooling problem. Submitted to J. Global Optimization. · Zbl 1392.90117
[12] Håstad J (1999) Clique is hard to approximate within n^{1-\epsilon}. Acta Mathematica 182:105-142.CrossRef · Zbl 0989.68060
[13] Haverly CA (1978) Studies of the behavior of recursion for the pooling problem. ACM SIGMAP Bull. 25:19-28.CrossRef
[14] McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I. Convex underestimating problems. Math. Programming 10(1):147-175.CrossRef · Zbl 0349.90100
[15] Meyer CA, Floudas CA (2006) Global optimization of a combinatorially complex generalized pooling problem. AIChE J. 52(3):1027-1037.CrossRef
[16] Misener R, Thompson JP, Floudas CA (2011) APOGEE: Global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Comput. Chemical Engrg. 35:876-892.CrossRef
[17] Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization (John Wiley & Sons, New York).CrossRef
[18] Pham V, Laird C, El-Halwagi M (2009) Convex hull discretization approach to the global optimization of pooling problems. Indust. Engrg. Chem. Res. 48(4):1973-1979.CrossRef
[19] Quesada I, Grossmann IE (1995) Global optimization of bilinear process networks with multicomponent flows. Comput. Chemical Engrg. 19(12):1219-1242.CrossRef
[20] Sherali HD, Adams WP (1998) A reformulation-linearization technique for solving discrete and continuous nonconvex problems. Nonconvex Optimization and Its Applications, Vol. 31 (Kluwer Academic Publishers, Dordrecht, the Netherlands).
[21] Tawarmalani M, Sahinidis NV (2002) Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, Chap. 9: The Pooling Problem (Kluwer Academic Publishers, Dordrecht, the Netherlands), 281-310.CrossRef
[22] Wicaksono DS, Karimi IA (2008) Piecewise MILP under- and overestimators for global optimization of bilinear programs. AIChE J. 54(4):991-1008.CrossRef
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.