(194g) Variable Bounds Tightening for Nonconvex MINLP with Application to Multiperiod Blending

Global optimization of nonconvex MINLPs is performed using branch-and-bound algorithms which involve solving convex relaxations of the original problem. The tightness of the convex relaxation strongly depends on the variable bounds.

Bounds tightening techniques have been implemented on general purpose MINLP solvers. A well-known technique is Optimality Based Bound Tightening (OBBT) which relies on solving LPs (Quesada and Grossmann 1995). While the tightest possible bounds can be obtained from such approach, it is computationally expensive. Ryoo and Sahinidis (Ryoo and Sahinidis 1996) proposed a bound tightening method based on reduced cost, which requires an optimal solution to the relaxed problem. Feasibility Based Bound Tightening (FBBT) considers a single constraint at a time to tighten variable bounds. Procedure that infers variable bounds using a pair of constraints has been proposed (Belotti 2013). Aggregating multiple constraints can lead to tighter variable bounds compared to FBBT while computationally inexpensive compared to OBBT. However, which constraints to be aggregated requires further investigation.

In this talk, we introduce an algorithm for variable bounds tightening using multiple constraints. We illustrate our methods in the context of Multiperiod Blending Problem (MBP) where streams are blended in blenders then sent to produce products with certain specifications. MBP is typically formulated as an MINLP. For example the source-based formulation involves bilinear terms for inventory splitting and binary variables for operating rules (Lotero et al. 2016). Starting from the source-based formulation, we propose a reformulation for the variables involved in the bilinear terms through lifting. We propose an algorithm to tighten the bounds for the lifted variables using linear constraints for stream availability, blender capacity, and product specifications. Specifically, we aggregate certain constraints to calculate bounds. Once a tighter bound for one variable is obtained, we use such bound to tighten bounds for other variables. The selection of constraints and the sequence of variable bounds to be tightened are based on the understanding of the physical system. The algorithm returns tighter bounds compared to FBBT, often as tight as OBBT. We introduce valid constraints derived from Reformulation-Linearization Technique (RLT) that utilize the bounds on the lifted variables to further tighten the formulation. We demonstrate the effectiveness of our methods in reducing optimality gap and solution time through an extensive computational study.

References

Belotti, Pietro. 2013. “Bound Reduction Using Pairs of Linear Inequalities.” Journal of Global Optimization 56 (3). Springer US:787–819. https://doi.org/10.1007/s10898-012-9848-9.

Lotero, Irene, Francisco Trespalacios, Ignacio E. Grossmann, Dimitri J. Papageorgiou, and Myun Seok Cheon. 2016. “An MILP-MINLP Decomposition Method for the Global Optimization of a Source Based Model of the Multiperiod Blending Problem.” Computers and Chemical Engineering. https://doi.org/10.1016/j.compchemeng.2015.12.017.

Quesada, I., and I.E. Grossmann. 1995. “Global Optimization of Bilinear Process Networks with Multicomponent Flows.” Computers & Chemical Engineering 19 (12). Pergamon:1219–42. https://doi.org/10.1016/0098-1354(94)00123-5.

Ryoo, Hong S., and Nikolaos V. Sahinidis. 1996. “A Branch-and-Reduce Approach to Global Optimization.” Journal of Global Optimization 8 (2). Kluwer Academic Publishers:107–38. https://doi.org/10.1007/BF00138689.