453300 Global Optimization of Crude Oil Scheduling with Discrete and Continuous-Time Formulations

Tuesday, November 15, 2016: 3:15 PM
Carmel II (Hotel Nikko San Francisco)
Pedro M. Castro, Centro de Matemática Aplicações Fundamentais e Investigação Operacional, Faculdade de Ciências, Universidade de Lisboa, Lisbon, Portugal

Optimization of scheduling operations in refineries has been recognized as a relatively inexpensive and fast way to improve key performance indices [1]. A distinctive feature of refinery scheduling problems is the blending of different types of crudes or liquid fuels for meeting quality specifications on process streams or customer orders. These are challenging problems since they involve modeling tanks of varying composition with non-convex bilinear terms, as well as complicating logistic constraints.

In this work, we focus on crude oil scheduling [2-8], which can be classified as a non-convex, mixed-integer nonlinear programming (MINLP) problem, belonging to one of the most complex fields in optimization [9]. Recent developments have occurred at the level of the: (i) mathematical formulation, with tighter source-based formulations for the closely related multi-period pooling problem of refined petroleum products [10,11]; (ii) global optimization algorithm, with efficient piecewise relaxation techniques [12,13]. The latter also include major performance improvements in the most recent versions of commercial solvers BARON [14] and GloMIQO [15].

In our previous work [8], a source-based continuous-time formulation was used underneath a rather complex Resource-Task Network (RTN) process model. The main novelty of this work is to present a simpler formulation by modelling logistic constraints through Generalized Disjunctive Programming (GDP) [9,16-17]. Furthermore, we also present its discrete-time counterpart. It should be highlighted that the discrete-time representation concept was part of the seminal paper [2] but has lost relevance in the last decade or so (when applied to this particular problem). The main motivation for revisiting discrete-time is that the inventory cost term in one of the two alternative objective functions considered becomes linear compared to continuous-time.

Results over a set of test problems from the literature show indeed that the discrete-time formulation is better when minimizing total cost, despite requiring an order of magnitude larger number of time slots. It was particularly surprising to find out that nonlinear scheduling problems with roughly 100 time points can be tackled to global optimality. On the other hand, the continuous-time approach is preferable when maximizing the gross margin.

The research study also involved the comparison of different global optimization algorithms. A two-stage MILP-NLP strategy relying on the standard McCormick relaxation [18] on the first iteration and on normalized multiparametric disaggregation [13] to close the gap, was shown competitive to commercial solvers BARON 16.3.4 and GloMIQO 2.3 for the objective of cost minimization. More specifically, the McCormick relaxation unexpectedly resulted in zero MILP relaxation gap when using a discrete-time formulation; (ii) normalized multiparametric disaggregation was slightly better when relying on continuous-time.

Acknowledgments: Financial support from Fundação para a Ciência e Tecnologia (FCT) through the Investigador FCT 2013 program and project UID/MAT/04561/2013.


[1] Kelly JD, Mann JL. Crude oil blend scheduling optimization: an application with multimillion dollar benefits-Part 1. Hydrocarbon Processing 2003; 82(6): 47.

[2] Lee H, Pinto JM, Grossman; IE, Park S. Mixed-integer linear programming model for refinery short-term scheduling of crude oil unloading with inventory management. Ind. Eng. Chem. Res. 1996; 35: 1630.

[3] Jia, Z, Ierapetritou M, Kelly JD. Refinery Short-term Scheduling Using Continuous Time Formulation: Crude-Oil Operations. Ind. Eng. Chem. Res. 2003; 42: 3085.

[4] Li J, Li W, Karimi IA, Srinivasan R. Improving the Robustness and Efficiency of Crude Scheduling Algorithms. AIChE J. 2007; 53: 2659-2680.

[5] Mouret S, Grossmann IE, Pestiaux P. A novel priority-slot based continuous-time formulation for crude-oil scheduling problems. Ind. Eng. Chem. Res. 2009; 48: 8515.

[6] Li J, Misener R, Floudas CA. Continuous-Time Modeling and Global Optimization Approach for Scheduling of Crude Oil Operations. AIChE J. 2012; 58: 205.

[7] Yadav S, Shaik MA. Short-Term Scheduling of Refinery Crude Oil Operations. Ind. Eng. Chem. Res. 2012; 51: 9287.

[8] Castro PM, Grossmann IE. Global Optimal Scheduling of Crude Oil Blending Operations with RTN Continuous-time and Multiparametric Disaggregation. Ind. Eng. Chem. Res. 2014; 53, 15127-15145.

[9] Trespalacios F, Grossmann IE. Review of Mixed-Integer Nonlinear and Generalized Disjunctive Programming Methods. Chem. Ing. Tech. 2014; 86(7): 991–1012.

[10] Castro PM. New MINLP Formulation for the Multiperiod Pooling Problem. AIChE J. 2015b; 61(11): 3728-3738.

[11] Lotero I, Trespalacios F, Grossmann IE, Papageorgiou DJ, 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. 2016; 87: 13-35.

[12] Kolodziej S, Castro PM, Grossmann IE. Global optimization of bilinear programs with a multiparametric disaggregation technique. Journal of Global Optimization 2013; 57: 1039-1063.

[13] Castro PM. Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problems. Journal of Global Optimization 2016; 64: 765-784.

[14] Tawarmalani M, Sahinidis NV. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming 2005; 103(2): 225-249.

[15] Misener R, Floudas CA. GloMIQO: Global mixed-integer quadratic optimizer. Journal of Global Optimization 2013; 57: 3-50.

[16] Balas E. Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems. SIAM J. Algebraic Discrete Methods. 1985; 6(3): 466-486.

[17] Raman R, Grossmann IE. Modeling and computational techniques for logic based integer programming. Comput. Chem. Eng. 1994; 18: 563-578.

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

Extended Abstract: File Not Uploaded
See more of this Session: Planning and Scheduling I
See more of this Group/Topical: Computing and Systems Technology Division