(514d) Deterministic Global Optimization of Large-Scale Pooling Problems Via Topological Branch-and-Bound

The pooling problem is an industrially-relevant nonconvex nonlinear optimization problem minimizing cost on a feed-forward network of input nodes, intermediate storage or pool nodes, and output nodes [1]. The difficulty of the pooling problem arises from the nonconvex bilinear terms representing linear blending in the pools. These bilinear terms, which track quality across the network, typically multiply flow rates by concentrations or flow fractions.

This work develops an algorithm that solves specialized pooling problem instances to global optimality and integrates the algorithm into a branch-and-bound framework for more generic instances. Beginning with simple sub-problems, we parameterize with respect to pool concentrations and find embedded polyhedral properties that generate disjunctive cuts for more meaningful test cases. These disjunctive cuts correspond to distinct network topologies and motivate a novel branch-and-bound algorithm based on the set of active network flows.

Each sub-restriction of the standard pooling problem can be represented I-L-J-K where I is the number of input feed nodes, L is the number of intermediate storage pool nodes, J is the number of output nodes, and K is the number of tracked qualities in the network. For example, case I-1-1-1 has an arbitrary number of input nodes, 1 pool node, 1 output node, and 1 tracked quality.

For restriction I-1-1-1 with no limits on feed availability or pool capacity, this work shows that at most 3 input nodes are active and analytically calculates the optimal solution. Extending to restriction I-1-J-1, we develop a polynomial-time algorithm based on solving a univariate polynomial. This polynomial-time algorithm generalizes and extends recent work analyzing computational complexity of the pooling problem [2â??4] since the analysis additionally integrates source-to-output streams and bounds on the network parameters. An interesting result is that subproblem I-1-J-1 preserves similar topological sparsity to I-1-1-1; there are at most J + 2 active input nodes for problems with no limits on feed availability or pool capacity. We also analyze several other limiting cases and thereby develop solution strategies for small problems that can be translated into effectively solving larger problems.

Transitioning from the polynomially solvable to the NP-hard instances, we design a topologically based branch-and-bound algorithm that branches on active network topologies and reduces the search space by eliminating infeasible topologies. Optimal flows are now simple to calculate for a fixed topology, so the topological branch-and-bound algorithm can avoid branching on the continuous variables in the pooling problem. We demonstrate the effectiveness of this method on a large number of problems including test cases in MINLPLib2 and the Dey and Gupte [5] test set. Further, we motivate how our results can extend from the pooling problem to any bilinear optimization problem based on process network topology.

This work is important for several reasons. First, we enable the solution of large scale pooling problems. Second, we are able to show why and how discretization is so useful for the pooling problem. Beginning in 2006, a significant body of work has shown that discretization from a nonconvex quadratically-constrained quadratic program (QCQP) into a mixed-integer linear program (MILP) is useful for generating rigorous lower bounds [6â??8] and primal heuristic solutions [5] for process networks problems with bilinear terms. Our parametric characterization of the pooling problem, which uncovers embedded polyhedrality and disjunctions, show why this strategy has been working to our advantage and motivates how to choose disjunctions for new problems.

[1] R Misener and CA Floudas. Advances for the pooling problem: Modeling, global optimization, and computational studies. Appl. Comput. Math., 8(1):3 â?? 22, 2009.

[2] D Haugland. The computational complexity of the pooling problem. J. Glob. Optim., 64(2), 199â??215, 2015.

[3] N Boland, T Kalinowski, and F Rigterink. A polynomially solvable case of the pooling problem. J. Glob. Optim., DOI: 10.1007/s10898-016-0432-6, 2016.

[4] D Haugland and EMT Hendrix. Pooling Problems with Polynomial-Time Algorithms. J. Optim. Theory Appl., DOI: 10.1007/s10957-016-0890-5, 2016.

[5] SS Dey and A Gupte. Analysis of MILP techniques for the pooling problem. Oper. Res., 63(2):412â??427, 2015.

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

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

[8] R Misener, JP Thompson, and CA Floudas. APOGEE: Global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Comput. Chem. Eng., 35(5):876â??892, 2011.