(314b) Using Functional Programming to Recognize Named Structure in an Optimization Problem: Application to Pooling

The pooling problem is a nonconvex nonlinear optimization problem with applications including [1]: crude oil scheduling [2], water networks [3], natural gas production [4], fixed-charge transportation with product blending [5], hybrid energy systems [6], and multi-period blend scheduling [7]. It is possible to integrate additional complexity into the pooling problem, e.g., allowing mutable topological decisions [8] or nonlinear blending rules [9]. A wide variety of pooling variants with generic process networks applications can be found in MINLPLib.

In solving process networks optimization problems there is a common theme: it is much easier to solve large-scale instantiations of the standard, archetypal pooling problem than it is to solve variants including mutable topology, nonlinear blending, or temporal aspects. For example, a recent primal heuristic performs consistently well on the order of 10k variables and constraints [10], but the approach exploits the standard pooling network structure and does not apply to pooling variants.

Previous work in mixed-integer linear optimization (MILP) has found that using network structure can significantly help generate strong cutting planes [11]. Automatically identifying these embedded networks in large-scale optimization models is NP-hard [12], but there exist several polynomial time approximation algorithms to find good networks [13]. State-of-the-art MILP solver software, such as CPLEX uses preprocessing heuristics to automatically find these network patterns. More recent work has considered detecting more complex structures such as multi-commodity flow [14].

This manuscript proposes automatically recognizing pooling structure within a mixed integer nonlinear optimization problem (MINLP). The pooling structure inside of a generic process optimization problem is a subset of the entire problem, so specialized, pooling-specific, cutting planes will also be valid bounds for the entire process networks problem. We also show that primal heuristic solutions to the standard pooling problem would be a good starting point for primal heuristics for the entire optimization problem.

Identifying pooling problem structure hinges on pattern matching. Patterns are defined by which variables and coefficients are expected in a constraint and by constraint bounds. The implementation is in F#, a strongly typed functional programming language targeting the .NET runtime environment. Pattern matching, one of the most distinctive F# features, has many uses, from decomposing data to control flow. The core concept is defining how data is expected to look and acting accordingly.

We tested the implementation on 3 sets of input OSiL files: the 70 large-scale standard pooling Dey and Gupte [10] examples, the 16 standard and extended Misener et al. [15] examples, and the 1342 MINLPLib test cases. For each test set, we read in a flat optimization problem and try to produce a pooling network. The implementation successfully deduces the original network structure for all 70 Dey and Gupte [10] examples, i.e., large-scale, standard pooling problems with up to 40 input, 30 pool, and 50 output nodes. Running our implementation on the 1342 test cases in MINLPLib2, 3 produce complete pooling problems and 78 more produce a pooling-like network. We also show that, after detecting the pooling problem in the flat MINLP, we can apply a good heuristic approach to get a good approximation solution.

References:

[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] J Li, A Li, IA Karimi, and R Srinivasan. Improving the robustness and efficiency of crude scheduling algorithms. AIChE J., 53(10):2659â??2680, 2007.

[3] B Galan and IE Grossmann. Optimal design of distributed wastewater treatment networks. Ind. Eng. Chem. Res., 37(10):4036 â?? 4048, 1998.

[4] X Li, E Armagan, A Tomasgard, and PI Barton. Stochastic pooling problem for natural gas production network design and operation under uncertainty. AIChE J., 57(8):2120â??2135, 2011.

[5] DJ Papageorgiou, A Toriello, GL Nemhauser, and MWP Savelsbergh. Fixed-charge transportation with product blending. Transport. Sci., 46(2):281â??295, 2012.

[6] RC Baliban, JA Elia, R Misener, and CA Floudas. Global optimization of a MINLP process synthesis model for thermochemical based conversion of hybrid coal, biomass, and natural gas to liquid fuels. Comput. Chem. Eng., 42:64 â?? 86, 2012.

[7] SP Kolodziej, IE Grossmann, KC Furman, and NW Sawaya. A discretization-based approach for the optimization of the multiperiod blend scheduling problem. Comput. Chem. Eng., 53:122 â?? 142, 2013.

[8] R Misener and CA Floudas. Global optimization of large-scale pooling problems: Quadratically constrained MINLP models. Ind. Eng. Chem. Res., 49(11):5424 â?? 5438, 2010.

[9] R Misener, CE Gounaris, and CA Floudas. Mathematical modeling and global optimization of large-scale extended pooling problems with the (EPA) complex emissions constraints. Comput. Chem. Eng., 34(9):1432 â?? 1456, 2010.

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

[11] TJ Van Roy and LA Wolsey. Solving mixed integer programming problems using automatic reformulation. Oper. Res., 35(1):45 â?? 57, 1987.

[12] GG Brown and WG Wright. Automatic identification of embedded network rows in large-scale optimization models. Math. Program., 29(1):41 â?? 56, 1984.

[13] RE Bixby and R Fourer. Finding embedded network rows in linear programs I. extraction heuristics. Manag. Sci., 34(3):342â??376, 1988.

[14] T Achterberg and C Raack. The MCF-separator: Detecting and exploiting multi-commodity flow structures in MIPs. Math. Program. Comput., 2(2):125â??165, 2010.

[15] 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.