(314b) Using Functional Programming to Recognize Named Structure in an Optimization Problem: Application to Pooling
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 , 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 . Automatically identifying these embedded networks in large-scale optimization models is NP-hard , but there exist several polynomial time approximation algorithms to find good networks . 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 .
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  examples, the 16 standard and extended Misener et al.  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  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.
 R Misener and CA Floudas. Advances for the pooling problem: Modeling, global optimization, and computational studies. Appl. Comput. Math., 8(1):3 â?? 22, 2009.
 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.
 B Galan and IE Grossmann. Optimal design of distributed wastewater treatment networks. Ind. Eng. Chem. Res., 37(10):4036 â?? 4048, 1998.
 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.
 DJ Papageorgiou, A Toriello, GL Nemhauser, and MWP Savelsbergh. Fixed-charge transportation with product blending. Transport. Sci., 46(2):281â??295, 2012.
 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.
 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.
 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.
 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.
 SS Dey and A Gupte. Analysis of MILP techniques for the pooling problem. Oper. Res., 63(2):412â??427, 2015.
 TJ Van Roy and LA Wolsey. Solving mixed integer programming problems using automatic reformulation. Oper. Res., 35(1):45 â?? 57, 1987.
 GG Brown and WG Wright. Automatic identification of embedded network rows in large-scale optimization models. Math. Program., 29(1):41 â?? 56, 1984.
 RE Bixby and R Fourer. Finding embedded network rows in linear programs I. extraction heuristics. Manag. Sci., 34(3):342â??376, 1988.
 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.
 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.