Using functional programming to recognize named structure in an optimization problem: Application to pooling
Author(s)
Ceccon, F
Misener, R
Type
Conference Paper
Abstract
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.
Date Issued
2016-11-13
Date Acceptance
2016-11-01
Citation
Computing and Systems Technology Division 2016 - Core Programming Area at the 2016 AIChE Annual Meeting, 2016, pp.363-365
ISBN
9781510834323
Publisher
American Institute of Chemical Engineers
Start Page
363
End Page
365
Journal / Book Title
Computing and Systems Technology Division 2016 - Core Programming Area at the 2016 AIChE Annual Meeting
Copyright Statement
© American Institute of Chemical Engineers. All rights reserved.
Sponsor
Royal Academy Of Engineering
Engineering & Physical Science Research Council (E
Grant Number
10216/118
EP/M028240/1
Source
2016 AIChE Annual Meeting
Publication Status
Published
Start Date
2016-11-13
Finish Date
2016-11-18
Coverage Spatial
San Francisco, CA