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 problem

^{1}, 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 problem^{1-4}. The p-formulation^{1} is perhaps the most intuitive, featuring total flows and compositions as model variables. The more recent tp-formulation by Alfaki and Haugland^{4} 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 generalized^{5} and extended^{6} but is aimed at steady state operation. In reality, however, supply and demand vary with time, resulting in a multiperiod blending problem^{7}. 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 problem^{8-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 work^{13}, 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-formulation^{4}, 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 divide^{9} the problem into MILP and NLP components, as well as by commercial solvers. In fact, BARON^{14} 14.0 and GloMIQO^{15} 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 disaggregation^{16-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.

References:

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 Group/Topical: Computing and Systems Technology Division