(398b) Global Optimization of Bilinear Programs with a Multiparametric Disaggregation Technique

The global optimization of bilinear programming problems is important in such areas as water networks and petroleum blending operations (e.g. Haverly, 1978; Bagajewicz, 2000; Misener et al, 2011). Nonconvex, bilinear constraints are required to model the mixing of various streams in these systems, and are in some cases the only nonlinearities in the models. The pooling problem, stemming from the original Haverly paper, contains these bilinear constraints and has received much attention in the literature. Recently, Misener & Floudas (2011) have demonstrated a novel logarithmic relaxation for modeling bilinear terms with piecewise McCormick envelopes while addressing various classes of pooling problems. Water network optimization problems containing bilinear terms have also received much attention in the literature (see Jezowski, 2010 for a review). The same blending constraints present in the pooling problem are present in water network problems, and thus numerous advances in solving bilinear programs have been made addressing these problems.

In this paper we present the derivation of the multiparametric disaggregation technique (MDT) by Teles et. al (2011) for solving nonconvex bilinear programs. The basic idea relies on a mixed-integer linear programming approximation that is based on a novel discretization scheme in which a discretized variable in the bilinear term is represented by a sum of digits over different powers. While commonly a base of 10 is used, the use of other bases is also possible (Teles et al. 2012), e.g. base 2. We derive both upper and lower bounding formulations corresponding to mixed-integer linear programs that are derived using disjunctive programming and exact linearizations. These are then incorporated into two global optimization algorithms that are used to solve bilinear programming problems. The extension to mixed-integer bilinear programs is also discussed.

First, a set of small problems is considered in order to compare the MDT with piece-wise McCormick convex envelopes. The results show that the relaxation derived using the MDT is shown to scale much more favorably (i.e. linearly vs. exponentially) than the relaxation that relies on piecewise McCormick envelopes, yielding smaller mixed-integer problems and faster solution times for similar optimality gaps. The proposed relaxation also compares well with general global optimization solvers on large problems.

Finally, we present results on both large-scale water network problems and multiperiod blending problems to show that the proposed MDT is competitive, and often more efficient that the direct use of general optimization solvers such as BARON and GloMIQO.

References

Bagajewicz, M.: A review of recent design procedures for water networks in refineries and process plants. Computers & Chemical Engineering 24(9–10), 2093-2113 (2000)

Haverly, C. A.: Studies of the behavior of recursion for the pooling problem. SIGMAP Bull. 25, 19-28 (1978)

Jeżowski, J.: Review of Water Network Design Methods with Literature Annotations.  Industrial & Engineering Chemistry Research 49 (10), 4475-4516 (2010)

Karuppiah, R., Grossmann, I.E.: Global optimization for the synthesis of integrated water systems in chemical processes. Computers and Chemical Engineering 30, 650-673 (2006).

Misener, R., Thompson, J.P., Floudas, C.A. APOGEE: Global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes, Computers & Chemical Engineering, 35(5), 876-892 (2011)

Teles, J.P., Castro, P.M., Matos, H.A. Multiparametric disaggregation technique for global optimization of polynomial programming problems. Journal of Global Optimization doi: 10.1007/s10898-011-9809-8 (2011).

Teles, J.P., Castro, P.M., Matos, H.A.: Global Optimization of Water Networks Design using Multiparametric Disaggregation. Computers and Chemical Engineering 40, 132-147 (2012).