(78f) Large-Scale Global Optimization of Generalized and Extended Pooling Problems: Methods and Computational Tools

The pooling problem, an optimization challenge of maximizing profit subject product availability, storage capacity, demand, and product specification constraints, has applications to petroleum refining, wastewater treatment, supply-chain operations, and communications [10]. Our recent work globally optimized two classes of pooling problems: (i) a generalized pooling problem that treats the network topology as a decision variable [11] and (ii) an extended pooling problem that incorporates the Environmental Protection Agency (EPA) Title 40 Code of Federal Regulations Part 80.45: Complex Emissions Model into the constraint set [12]. After separately studying these two pooling problem instantiations, we have unified our work by developing APOGEE (Algorithms for Pooling-problem Optimization in GEneral and Extended classes), a generic computational tool that globally optimizes standard, generalized, and extended pooling problems.

The generalized pooling problem increases the complexity of the pooling problem by transforming the network topology into a decision variable [1, 9, 11]. Choosing the interconnections between process units and storage tanks, or pools, is combinatorially complex. Because the activation or deactivation of each pipe or intermediate node is a discrete decision and the linear mixing at the intermediate nodes leads to bilinear terms, the generalized pooling problem is a mixed-integer nonconvex program (nonconvex MINLP) with quadratic equalities and inequalities which exhibits multiple locally optimal solutions. The major challenge in this problem is developing of rigorous global optimization methods that address large scale problems to global optimality.

We revisited the generalized pooling problem test cases of Meyer and Floudas [9, 11]. These test cases posit a set of wastewater sources containing regulated qualities that must be treated before release into the environment [2]. Representing the challenges that industry faces, we then considered as many as twenty treatment options and allowed the possibility of interconnections between all the treatment plants. We exploited recent advances in piecewise-linear underestimation of bilinear terms [3, 5, 6, 7, 9, 13, 14, 17] within a branch-and-bound algorithm and globally optimized these test cases.

The extended pooling problem is a mixed-integer nonlinear model (MINLP) that appends the Environmental Protection Agency (EPA) Title 40 Code of Federal Regulations Part 80.45: Complex Emissions Model and associated legislative constraints to a standard pooling problem. The goal is to comply with reformulated gasoline standards while maximizing profitability. After constructing a mixed-integer nonlinear model (MINLP) of the extended pooling problem [12], with nonconvex constraints including bilinear, multilinear, exponential, and power law terms [4], we developed a linear relaxation of the MINLP using piecewise-linear [3, 5, 6, 7, 9, 13, 14, 17] and edge-concave [8, 15, 16] relaxations. We integrated these relaxations into a branch-and-bound algorithm and solved several test cases to global optimality.

Finally, we present recent developments on the computational platform and software package APOGEE that globally optimizes all classes of pooling problems. We have integrated our computational studies on piecewise-linear and edge-concave underestimators with our modeling experience on the standard, generalized, and extended pooling problems to generically address all three classes of pooling problems. We describe APOGEE and demonstrate its performance on all three classes of pooling problems.

[1] C. Audet, J. Brimberg, P. Hansen, S. Le Digabel, and N. Mladenovic. Pooling problem: Alternate formulations and solution methods. Manage. Sci., 50(6):761 ? 776, 2004.

[2] M. Bagajewicz. A review of recent design procedures for water networks in refineries and process plants. Comput. Chem. Eng., 24:2093 ? 2113, 2000.

[3] M. L. Bergamini, I. Grossmann, N. Scenna, and P. Aguirre. An improved piecewise outer-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms. Comput. Chem. Eng., 32(3):477 ? 493, 2008.

[4] K. C. Furman and I. P. Androulakis. A novel MINLP-based representation of the original complex model for predicting gasoline emissions. Comput. Chem. Eng., 32:2857?2876, 2008.

[5] C. E. Gounaris, R. Misener, and C. A. Floudas. Computational comparison of piecewise-linear relaxations for pooling problems. Ind. Eng. Chem. Res., 48(12):5742 ? 5766, 2009.

[6] M. M. F. Hasan and I. A. Karimi. Piecewise linear relaxation of bilinear programs using bivariate partitioning. AIChE J., 2010. Forthcoming (DOI: 10.1002/aic.12109).

[7] R. Karuppiah and I. E. Grossmann. Global optimization for the synthesis of integrated water systems in chemical processes. Comput. Chem. Eng., 30:650?673, 2006.

[8] C. A. Meyer and C. A. Floudas. Convex envelopes for edge-concave functions. Math. Program., 103(2):207?224, 2005.

[9] C. A. Meyer and C. A. Floudas. Global optimization of a combinatorially complex generalized pooling problem. AIChE J., 52(3):1027 ? 1037, 2006.

[10] R. Misener and C. A. Floudas. Advances for the pooling problem: Modeling, global optimization, and computational studies. Applied and Computational Mathematics, 8(1):3 ? 22, 2009.

[11] R. Misener and C. A. Floudas. Global optimization of large-scale generalized pooling problems: Quadratically constrained MINLP models. Ind. Eng. Chem. Res., 2010. Forthcoming.

[12] R. Misener, C. E. Gounaris, and C. A. Floudas. Mathematical modeling and global optimization of large-scale extended pooling problems with the (EPA) complex emissions constraints. Comput. Chem. Eng., 2010. Forthcoming (DOI: 10.1016/j.compchemeng.2010.02.014).

[13] V. Pham, C. Laird, and M. El-Halwagi. Convex hull discretization approach to the global optimization of pooling problems. Ind. Eng. Chem. Res., 48:1973 ? 1979, 2009.

[14] Y. Saif, A. Elkamel, and M. Pritzker. Global optimization of reverse osmosis network for wastewater treatment and minimization. Ind. Eng. Chem. Res., 47(9):3060 ? 3070, 2008.

[15] F. Tardella. On a class of functions attaining their maximum at the vertices of a polyhedron. Discret. Appl. Math., 22:191?195, 1988/89.

[16] F. Tardella. On the existence of polyhedral convex envelopes. In C. A. Floudas and P. M. Pardalos, editors, Frontiers in Global Optimization, 563?573. Kluwer Academic Publishers, 2003.

[17] D. S. Wicaksono and I. A. Karimi. Piecewise MILP under-and overestimators for global optimization of bilinear programs. AIChE J., 54(4):991?1008, 2008.