(715g) Preprocessing Algorithms and Tightening Constraints for Blend Scheduling Models

Yifu Chen, Christos T. Maravelias

Department of Chemical and Biological Engineering, University of Wisconsin-Madison

1415 Engineering Dr., Madison, WI 53706, USA

The multiperiod blend scheduling problem (MBSP) considers the scheduling in a production environment that includes blending processes, where streams with different properties are mixed (blended) to obtain products that satisfy given property specifications. MBSP can be considered as a scheduling extension of the well-studied pooling problem^1,2, or time-indexed pooling problem³. In general, MBSP is formulated as mixed integer nonlinear programming (MINLP) problem, where binary variables are used to model decisions on material transfers, and nonlinear constraints containing bilinear terms are employed to model the blending process.

Researchers have proposed a range of methods to address global optimization problem containing binary variables and bilinear terms in the context of pooling and blending problems over the past few decades, including decomposition, linear approximation, valid inequalities, as well as identifying parametric structures ^4–9. However, solving large MBSP remains challenging, partly due the weak models obtained after applying convex relaxation to the bilinear terms. Tightening methods based on strong valid inequalities and reformulations have been proven to be efficient to address instances of industrial relevance in chemical production scheduling problem^10,11 but have not been generalized for blending problems.

Accordingly, in this work we build upon the insights offered by tightening methods for mixed integer linear programming (MILP) scheduling models, to develop new tightening constraints for MBSP. The goal is to use instance-specific data, such as product demand and unit capacity, to tighten the formulation, and thereby obtain improvement in computational performance.

Specifically, we first introduce novel preprocessing algorithms, which can be executed in seconds, to calculate bounds on critical variables in MBSP. In particular, we propose lower bounds on demand for streams when given product demand and specifications, and upper bounds on production and streams utilization when stream availability is given. Second, we introduce new disaggregated variables for stream flows and define product dedicated flow variables to address product specific features involved in MBSP. Third, the bounds obtained from the preprocessing algorithms along with the new variables are used to generate tightening constraints. In some special cases, we show that some of the proposed tightening constraints coincide with a subset of the facet defining inequalities for fixed charge transportation problem with product blending¹².

The methods are applicable to both (1) final product blending and (2) crude oil blending, including downstream distillation units. Furthermore, they are applicable to all previously proposed MINLP models for MBSP, as well as MILP models obtained from the MINLP formulations using different linear relaxation/approximation methods. Finally, we discuss how they can be modified so they are applicable to both cost minimization for given demand, and profit maximization problems.

We close with a computational study including a wide range of (1) previously proposed MINLP and MILP models, (2) global optimization solvers, and (3) literature instances.

Reference

1. Kolodziej, S. P., Grossmann, I. E., Furman, K. C. & Sawaya, N. W. A discretization-based approach for the optimization of the multiperiod blend scheduling problem. Comput. Chem. Eng. 53, 122–142 (2013).
2. Lotero, I., Trespalacios, F., Grossmann, I. E., Papageorgiou, D. J. & Cheon, M. S. An MILP-MINLP decomposition method for the global optimization of a source based model of the multiperiod blending problem. Comput. Chem. Eng. 87, 13–35 (2016).
3. Gupte, A., Ahmed, S., Dey, S. S. & Cheon, M. S. Relaxations and discretizations for the pooling problem. J. Glob. Optim. 67, 631–669 (2017).
4. Meyer, C. A. & Floudas, C. A. Global optimization of a combinatorially complex generalized pooling problem. AIChE J. 52, 1027–1037 (2006).
5. D’Ambrosio, C., Linderoth, J. & Luedtke, J. Valid Inequalities for the Pooling Problem with Binary Variables. in Integer Programming and Combinatoral Optimization (eds. Günlük, O. & Woeginger, G. J.) 117–129 (Springer Berlin Heidelberg, 2011).
6. Li, J., Misener, R. & Floudas, C. A. Continuous-time modeling and global optimization approach for scheduling of crude oil operations. AIChE J. 58, 205–226 (2012).
7. Kolodziej, S. P., Castro, P. M. & Grossmann, I. E. Global optimization of bilinear programs with a multiparametric disaggregation technique. J. Glob. Optim. 57, 1039–1063 (2013).
8. Castillo, P. A. C., Mahalec, V. & Kelly, J. D. Inventory pinch algorithm for gasoline blend planning. AIChE J. 59, 3748–3766 (2013).
9. Baltean-Lugojan, R. & Misener, R. Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness. J. Glob. Optim. 1–36 (2017). doi:10.1007/s10898-017-0577-y
10. Velez, S., Sundaramoorthy, A. & Maravelias, C. T. Valid Inequalities Based on Demand Propagation for Chemical Production Scheduling MIP Models. AIChE J. 59, 872–887 (2013).
11. Merchan, A. F., Lee, H. & Maravelias, C. T. Discrete-time mixed-integer programming models and solution methods for production scheduling in multistage facilities. Comput. Chem. Eng. 94, 387–410 (2016).
12. Papageorgiou, D. J., Toriello, A., Nemhauser, G. L. & Savelsbergh, M. W. P. Fixed-Charge Transportation with Product Blending. Transp. Sci. 46, 281–295 (2012).