416376 A More Efficient Formulation for the Multiperiod Blending Problem

Thursday, November 12, 2015: 12:30 PM
Salon F (Salt Lake Marriott Downtown at City Creek)
Pedro M. Castro, Centro de Matemática Aplicações Fundamentais e Investigação Operacional, Faculdade de Ciências, Universidade de Lisboa, Lisbon, Portugal

Finding the most profitable blends of different distilled fractions so as to meet technical and environmental regulations is a problem of great importance in petroleum refineries. It become known as the pooling problem1, where the pools represent blending tanks whose content, generated from the mixing of fuels with known properties, is going to be determined by the optimization.

A few MINLP formulations have been proposed for the pooling problem1-4. The p-formulation1 is perhaps the most intuitive, featuring total flows and compositions as model variables.  The more recent tp-formulation by Alfaki and Haugland4 replaces the pool composition variables with the proportion of the pool being sent to each final product, which add up to one.

The original problem definition has been generalized5 and extended6 but is aimed at steady state operation. In reality, however, supply and demand vary with time, resulting in a multiperiod blending problem7. Models entities gain a time index, and tank capacity and logistic constraints (concerning the movement of materials into and out of tanks) need to be enforced.

The crude oil unloading and inventory management problem8-13 is closely related but more detailed in the sense that the duration of the time intervals is going to be determined by the optimization. In recent work13, we have shown that a Resource-Task Network continuous-time formulation can effectively capture the most important system constraints and be solved very efficiently by commercial global optimization solvers. The material resources are the different crudes and their location as they move from marine vessels to distillation columns, with the contents of a tank consisting of multiple crudes rather than a single resource of unknown composition. The challenge of enforcing that a tank’s outlet stream has the exact same composition of the blend inside the tank is then overcome through bilinear constraints featuring split fraction variables. These are similar to those used in the tp-formulation4, the difference being that the sum of the split fraction over all possible outlet streams does not add to one since some inventory may be left in the tank to be used in subsequent time periods, which does not apply to the steady-state pooling problem.

The main novelty of this work is to define the liquid fuels initially present in the system as new model entities and propose a new formulation with split fraction variables that keeps track of their location through time. Due to the discrete-time nature of the multiperiod blending problem (with static time periods), we can move away from the complex nomenclature of the RTN and present a model that is easier to understand.

Overall, the new formulation leads to a different set of non-convex bilinear terms compared to the original work of Kolodziej et al.7. Through the solution of a set of seven test problems from the literature (freely available online at www.minlp.org), we show that these are better handled by decomposition algorithms that divide9 the problem into MILP and NLP components, as well as by commercial solvers. In fact, BARON14 14.0 and GloMIQO15 2.3 can solve to global optimality all problems resulting from the new formulation. A tailored global optimization algorithm working with a tight mixed-integer relaxation from multiparametric disaggregation16-17 achieves a similar performance.

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. Haverly CA. Studies of the behavior of recursion for the pooling problem. SIGMAP Bulletin 1978; 25, 19–28.

2 Ben-Tal A, Eiger G, Gershovitz V. Global minimization by reducing the duality gap. Mathematical Programming, 1994; 63: 193–212.

3 Tawarmalani M, Sahinidis, NV. Convexification and global optimization in continuous and mixed-integer nonlinear programming: Theory, algorithms, software, and applications. Dordrecht: Kluwer Academic Publishers 2002, pp. 254–284.

4 Alfaki M, Haugland D. Strong formulations for the pooling problem. J Glob Optim 2013; 56: 897-916.

5. Meyer CA, Floudas CA. Global optimization of a combinatorially complex generalized pooling problem. AIChE J 2006; 52(3): 1027-1037.

6 Misener R, Floudas CA. Advances for the pooling problem: Modeling, global optimization, and computational studies. Applied and Computational Mathematics 2009; 8(1): 3–22.

7. Kolodziej SP, Grossmann IE, Furman KC, Sawaya NW. A discretization-based approach for the optimization of the multiperiod blend scheduling problem. Comput Chem Eng 2013; 53: 122-142.

8 Lee H, Pinto JM, Grossmann 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-1641.

9 Jia Z, Ierapetritou M, Kelly JD. Refinery short-term scheduling using continuous time formulation: Crude-oil operations. Ind Eng Chem Res 2003; 42: 3085-3097.

10 Furman K, Jia Z, Ierapetritou MG. A robust event-based continuous time formulation for tank transfer scheduling. Ind Eng Chem Res 2007; 46: 9126-9136.

11 Li J, Li W, Karimi IA, Srinivasan R. Improving the robustness and efficiency of crude scheduling algorithms. AIChE J 2007; 53: 2659-2680.

12 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-8528.

13 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.

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. J. Global Optimization 2013; 57: 3-50.

16 Teles JP, Castro PM, Matos HA. Multiparametric disaggregation technique for global optimization of polynomial programming problems. J Glob Optim 2013; 55: 227-251.

17 Kolodziej S, Castro PM, Grossmann IE. Global optimization of bilinear programs with a multiparametric disaggregation technique. J Glob Optim 2013; 57: 1039-1063.

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