(288b) A Spatial Branch & Bound Global Optimization Algorithm Featuring Multiparametric Disaggregation in the Relaxation Steps

We consider non-convex mixed-integer bilinear programs where binary variables appear linearly in the constraints. The global optimization of such problem is important in areas such as power systems, petroleum blending operations and process networks. Example of bilinear functions are: (i) the production cost term in the objective function of the thermal unit commitment problem [1]; (ii) the power output in hydro energy systems, related to water discharge and water storage [2]; (iii) the properties of a product resulting from a mix of materials, which can be estimated as weighted sums by concentration of their individual properties [3]. The binary variables in the formulation may have different origins: (a) accounting for system operation in multiple consecutive time periods, as in the power systems scheduling problems for the day-ahead electricity markets or in multiperiod blending operations [4]; (b) allowing for connections between units only if the flowrate exceeds a certain minimum value, as in generalized pooling [5-6] or water network design problems [7-8]; (c) choosing between alternative technologies for treatment units [9-10].

Most global optimization approaches for bilinear programs rely on the convex McCormick [11] envelopes, which provide a relaxation of the original problem. The quality of the relaxation is highly dependent on the lower and upper bounds of the variables involved in the bilinear terms, improving as their domain is partitioned. This can be done iteratively, as in spatial branch & bound frameworks [12-13] or simultaneously, using piecewise McCormick envelopes [6,9,14-15] or univariate parameterization techniques [16-17] (e.g. multiparametric disaggregation [18]).

One important property of multiparametric disaggregation is that the number of binary variables in the mixed-integer linear relaxation grows logarithmically with the number of discretization points, leading to an improved computational performance when compared to piecewise McCormick envelopes for an equivalent number of partitions [16]. However, increasing the quality of the relaxation by a ten-fold increase in the number of discretization points (from level p to p-1) may increase the complexity too much so that no reduction in the optimality gap is observed within a reasonable computational time. Provided that modest computational time is required to solve the problem for level p, one can still solve multiple instances of the problem for that same level in a reasonable time.

We thus propose to use multiparametric disaggregation in the bound contraction procedure to further reduce the domain of the variables when compared to the traditional way of using McCormick envelopes. This will precede the solution of the lower bounding formulations that are a relaxation of the original minimization problem, allowing us to achieve smaller optimality gaps. A spatial branch & bound algorithm also relying on multiparametric disaggregation then further reduces the gap. The variable selected for branching is the one leading to the largest error of the bilinear term, with range reduction being done through bisection.

Taking short-term scheduling problems of hydro power systems (MINLP) together with water-using network design problems (NLP) as case studies, we show that the proposed global optimization solver performs better than commercial global optimization solvers.

References:

[1]- Carrión M, Arroyo JM. A Computationally Efficient Mixed-Integer Linear Formulation for the Thermal Unit Commitment Problem. IEEE Transactions on Power Systems 2006; 21 (3), 1371-1378.

[2] Catalão JPS, Pousinho HMI, Mendes VMF. Hydro energy systems management in Portugal: Profit-based evaluation of a mixed-integer nonlinear approach. Energy 2011; 36: 500-507.

[3] Quesada I, Grossmann IE. Global optimization of bilinear process networks with multicomponent flows. Computers & Chemical Engineering 1995; 19, 1219-1242.

[4] Kolodziek SP, Grossmann IE, Furman KC, Sawaya NW. A Discretization-based Approach for the Optimization of the Multiperiod Blend Scheduling Problem. Computers and Chemical Engineering 2013. Doi: 10.1016/j.compchemeng.2013.01.016.

[5] Meyer CA, Floudas CA. Global Optimization of a Combinatorially Complex Generalized Pooling Problem. AIChE Journal 2006; 52 (2), 1027-1037.

[6] Misener R, Thompson JP, Floudas CA. APOGEE: Global Optimization of Standard, Generalized, and Extended Pooling Problems via Linear and Logarithmic Partitioning Schemes. Computers & Chemical Engineering 2011; 35, 876-892.

[7] Jezowski J. Review of water network design methods with literature annotations. Industrial & Engineering Chemistry Research 2010; 49, 4475-4516.

[8] Faria DC, Bagajewicz MJ. A New Approach for Global Optimization of a Class of MINLP Problems with Applications to Water Management and Pooling Problems.

[9] Karuppiah R, Grossmann IE. Global optimization for the synthesis of integrated water systems in chemical processes. Computers and Chemical Engineering 2006; 30, 650-673.

[10] Nápoles-Rivera F, Ponce-Ortega JM, El-Halwagi MM, Jiménez-Gutiérrez A. Global Optimization of Mass and Property Integration Networks with In-Plant Property Interceptors. Chemical Engineering Science 2010; 65, 4363-4377.

[11] McCormick GP. Computability of global solutions to factorable nonconvex programs. Part I. Convex underestimating problems. Mathematical Programming 1976; 10, 147-175.

[12] Ryoo HS, Sahinidis NV. A branch-and-reduce approach to global optimization. Journal of Global Optimization 1996; 8, 201-205.

[13] Misener R, Floudas CA. GloMIQO: Global Mixed-Integer Quadratic Optimizer. Journal of Global Optimization, doi:10.1007/s10898-012-9874-7.

[14] Bergamini ML, Aguirre P, Grossmann IE. Logic-based outer approximation for globally optimal synthesis of process networks. Computers and Chemical Engineering 2005; 29, 1914-1933.

[15] Wicaksono DN, Karimi IA. Piecewise MILP Under- and Overestimators for Global Optimization of Bilinear Programs. AIChE Journal 2008; 54, 991-1008.

[16] Kolodziej S, Castro PM, Grossmann IE. Global Optimization of Bilinear Programs with a Multiparametric Disaggregation Technique. Journal of Global Optimization 2013. doi: 10.1007/s10898-012-0022-1.

[17] Teles JP, Castro PM, Matos HA. Univariate Parameterization for Global Optimization of Mixed-Integer Polynomial Problems. European Journal of Operation Research. htpp://dx.doi.org/10.1016/j.ejor.2013.03.042.

[18] Teles JP, Castro PM, Matos HA. Multiparametric disaggregation technique for global optimization of polynomial programming problems. Journal of Global Optimization 2013; 55, 227-251