(522b) Deterministic Global Optimization Algorithm Using Piecewise Relaxations and Bound Tightening with Dynamic Partitioning

Deterministic global optimization algorithms can compute a ε-global solution for nonconvex optimization problems, where ε is the difference between the best feasible solution found and an estimate of the theoretical optimum. To compute such estimates, deterministic global optimization algorithms relax the original nonconvex problem into either a linear (LP), a mixed-integer linear (MILP), or a convex nonlinear program (NLP). The relaxation scheme can be derived using: convex envelopes, piecewise linear relaxations, αBB underestimators, the reformulation-linearization technique, by removing integrality constraints, etc. To iteratively improve the estimate of the global optimum, one can rely on spatial branch-and-bound [1], cutting planes [2], bound tightening [3,4], interval elimination strategies [5], and increasing number of partitions of piecewise relaxations [6]. To compute feasible solutions, information from the relaxation is often used by single/multistart NLP strategies and other heuristic techniques.

Bilinear terms are the product of two different variables and are very common in planning models for industrial processes, appearing in material balances, blending equations, and energy balances. For bilinear terms, McCormick envelopes [7]provide the tightest linear relaxation. Piecewise relaxation techniques partition the domain of one of the variables in a bilinear term, so as to benefit from tighter, partition-dependent bounds. However, they require the addition of extra binary variables (and continuous) to identify the optimal partition. The larger the number of partitions, the tighter the relaxation (i.e., the closer to the original nonconvex model) and the higher the computational cost to solve it to optimality. Two common piecewise relaxation techniques are piecewise McCormick (PMCR) [6,8] and normalized multiparametric disaggregation (NMDT) [6]. PMCR constructs McCormick envelopes for each partition, while NMDT uses a different formulation that requires fewer number of binary variables than PMCR for the same partitioning level. It has been shown that NMDT presents a computational advantage over PMCR when the number of partitions is equal to or greater than 10 [6].

Bound tightening techniques can also be used to improve the relaxation by reducing the domain of the variables involved in nonlinear terms. Optimality-based bound tightening (OBBT) involves solving one minimization and one maximization problem for each variable. These optimization problems can be solved sequentially [9] or in parallel [10]. In a branch-and-bound algorithm, OBBT can be applied at each node in order to reduce the number of nodes to explore and the final optimality gap [11]. Since OBBT is very effective but requires significant computational effort, accelerating and approximation techniques have been proposed for OBBT in a branch-and-bound framework [12].

In this work, we propose a deterministic global optimization algorithm for mixed-integer bilinear programming problems that works by dynamically partitioning piecewise relaxations. The proposed algorithm starts by partitioning all the variables from bilinear terms using PMCR with 2 partitions. The resulting MILP relaxation (denoted as model PR) with NPR partitions is solved using CPLEX with the solution pool option active. The stored solutions are employed as starting points for a local nonlinear solver (in this case CONOPT) in a multistart strategy implemented in parallel fashion. If the termination criterion is not met, the algorithm will continue by increasing NPR. Whenever the number of partitions reaches 10, PMCR is replaced by NMDT. If model PR cannot be solved to optimality within the allocated time, the algorithm reverts back to the previous smaller number of partitions.

OBBT is used extensively. It is applied in each iteration using a relaxation (denoted as PRB) with NPRB partitions, starting with NPRB = 1 (i.e., standard McCormick envelopes). Whenever NPR is increased, NPRB remains the same. If NPR remains constant, NPRB is increased by 1. The algorithm goes back to increase NPR when the domain of the variables cannot be reduced significantly. Parallelization of the OBBT step is used to reduce wall execution times.

In summary, the proposed algorithm focuses more at the beginning on model PR than in the bound tightening procedure. Small problems are usually solved faster by increasing the number of partitions NPR than by applying OBBT several times. Then, the algorithm seeks to exploit the OBBT procedure to a major extent when the size of model PR becomes too large.

The algorithm was tested on seven examples from a refinery planning model considering different demand scenarios and number of time periods [10], and three scheduling examples from a hydro energy system considering different number of reservoirs [3]. The refinery planning problems feature few binary variables (12 to 36) but large number of bilinear terms (476 to 1608), while the hydro scheduling problems have significant number of binary variables (96 to 336) and twice as many bilinear terms. Results show that the proposed algorithm computes smaller optimality gaps than commercial global solvers BARON and ANTIGONE for the hydro scheduling problems within the same allocated execution time, and the same or better optimality gaps for the refinery planning problems. These results indicate that using piecewise relaxations with dynamic partitioning to compute estimates of the global optimum and bound-tightening is a promising strategy in the development of global optimization algorithms. Future work will be to include relaxation techniques for other types of nonlinear terms, as well as to determine if our proposed strategy can be complemented by a spatial branch-and-bound method.

References

[1] Quesada I, Grossmann IE. Global optimization of bilinear process networks with multicomponent flows. Comput Chem Eng.1995; 19(12): 1219-1242.

[2] Karuppiah R, Furman KC, Grossmann IE. Global optimization for scheduling refinery crude oil operations. Comput Chem Eng.2008; 32(11): 2745-2766.

[3] Castro PM, Grossmann IE. Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems. J Glob Optim. 2014; 59(2-3), 277-306.

[4] Yang Y, Barton PI. Refinery optimization integrated with a nonlinear crude distillation unit model. IFAC-PapersOnLine. 2015; 48(8): 205-210.

[5] Faria DC, Bagajewicz MJ. A new approach for global optimization of a class of MINLP problems with applications to water management and pooling problems. AIChE J.2012; 58(8): 2320-2335.

[6] Castro PM. Normalized multiparametric disaggregation: An efficient relaxation for mixed-integer bilinear problems. J Glob Optim. 2016; 64(4): 765-784.

[7] McCormick GP. Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math Program.1976; 10(1): 147-175.

[8] Bergamini ML, Aguirre P, Grossmann IE. Logic-based outer approximation for globally optimal synthesis of process networks. Comput Chem Eng. 2005; 29(9): 1914-1933.

[9] Castro PM. Tightening piecewise McCormick relaxations for bilinear problems. Comput Chem Eng. 2015; 72: 300-311.

[10] Castillo Castillo PA, Castro PM, Mahalec V. Global optimization algorithm for large-scale refinery planning models with bilinear terms. Ind Eng Chem Res. 2016; 56(2): 530-548.

[11] Castro PM. Spatial branch-and-bound algorithm for MIQCPs featuring multiparametric disaggregation. Optim Method Softw. 2017. DOI: http://dx.doi.org/10.1080/10556788.2016.1264397

[12] Gleixner AM, Berthold T, Muller B, Weltge S. Three enhancements for optimization-based bound tightening. J Glob Optim. 2017; 67:731–757.