(456f) A Novel Deterministic Global Optimization Algorithm and Its Application to Oil Refinery Planning

Castillo Castillo, P., McMaster University
Mahalec, V., McMaster University
Castro, P. M., Faculdade de Ciências, Universidade de Lisboa
A petroleum refinery separates crude oils into various fractions with different quality properties (e.g. density, sulfur content, octane number, etc.). Such fractions are then transformed into intermediate products by chemical processes and they are either sold, used as raw materials for another process, or used as blend components for liquid fuels (e.g. gasoline, kerosene, and diesel).

One of the main issues regarding production planning of an oil refinery is the nonlinear nature of the processes involved. By assuming the processes to be linear, inaccuracy of the resulting model can make the solution suboptimal or unsuitable for real life applications. Current trend is to develop nonlinear planning models that are more accurate but that can be solved in a reasonable time. Li et al.1 developed nonlinear models for the crude distillation unit (CDU) and the fluidize-bed catalytic cracker and integrated them into the refinery planning problem. Alhajri et al.2 proposed a swing cut method for the CDU based on a polynomial formulation and fractional polynomials for the processing unit models. Alattas et al.3 presented a nonlinear model for the CDU based on the fractionation index of a distillation column. Menezes et al.4 formulated a swing-cut method that accounts for the difference in quality of the light and heavy splits of a swing cut fraction. Fu et al.5 developed a hybrid nonlinear model for the CDU that predicts the true boiling point (TBP) curves of the products via partial least squares model with feed TBP curve and column operating conditions as inputs. Li et al.described a least-squares methodology to use data-based nonlinear models for the processing units. If the planning model is nonconvex, then global optimization techniques are required to avoid computing a local solution far from the true optimum.

Deterministic global optimization algorithms compute feasible solutions as well as estimates of the best possible solution. These estimates are computed by relaxing the original nonconvex problem into a convex one. The main idea in deterministic global optimization algorithms is to reduce the difference between the best feasible solution and the estimate of the best possible solution to less than a non-zero tolerance value ε. To improve the quality of the estimates of the global optimum, the tightness of the relaxed model is usually increased by employing a spatial branch-and-bound strategy7, addition of cutting planes8, reducing the domain of the variables9,10, and/or by increasing the number of partitions in the case of piecewise relaxation techniques11. Feasible solutions are usually computed using information from the convex model solution.

Bilinear terms (i.e. the product of two variables) are very common in planning models; for example, in material balances (mass or volume times concentration) and blending equations (mass or volume times a quality property). For bilinear terms, McCormick envelopes12 provide the tightest linear relaxation. Piecewise linear relaxation techniques discretize the range of one of the variables involved in a bilinear term and then construct convex envelopes for each partition. Piecewise linear relaxations are tighter than simple linear ones; however, they introduce binary variables (making the relaxed model a mixed-integer linear program or MILP) and thus a trade-off between quality of the relaxed model and the computational effort required to solve it to optimality. Piecewise McCormick relaxation (PMCR) is a well-known technique of this type; it constructs McCormick envelopes for each partition. Normalized multiparametric discretization technique (NMDT) is a method recently developed11 and it requires fewer number of binary variables than PMCR for the same discretization level.

We propose a deterministic global optimization algorithm for mixed-integer nonlinear programming (MINLP) problems, where nonlinearities are due to quadratic and bilinear terms. It relies on discretizing the nonlinear terms dynamically using either PMCR or NMDT. The resulting MILP model is solved using CPLEX and several feasible solutions are stored in CPLEXâ??s solution pool and employed as starting points for a local nonlinear solver (e.g. CONOPT). These nonlinear models are solved in parallel. Then, the estimate of the global solution and the best feasible solution are updated. If the relative difference between these two (i.e. the optimality gap) is smaller than ε, then the algorithm stops; otherwise, it continues by reducing the range of the variables or increasing the number of partitions for the next iteration. If there is an improvement in the best feasible solution, then the domain of the variables involved in nonlinear terms is reduced using an optimality-based bound tightening (OBBT) method. This OBBT method consists in solving two optimization problems for each variable: a maximization and a minimization of the range of the variable subject to the MILP relaxation constraints. Parallelization of this step is required to avoid long execution times.

The algorithm was tested on several examples of a refinery planning model considering different demand scenarios and number of time periods. The refinery system comprises a crude distillation unit, a catalytic reformer, a hydrocracker, a fluid catalytic cracking unit, 5 hydrotreaters, 3 blenders, 5 products, 19 blend components, 8 quality properties, and a planning horizon of 7 days. Results show that the algorithm outperforms commercial solver BARON13 and performs at least as well as commercial solver ANTIGONE14 when handling large-scale multiperiod problems. For large-scale problems, increasing the number of partitions leads to larger MILP models, which are more accurate but cannot be solved to optimality. The major improvements in these examples are observed after applying OBBT method and solving the MILP model with the same number of partitions. Future work will be to improve efficiency of OBBT method in order to reduce execution times. Finally, the proposed algorithm can be applied to other problems by selecting and including the required convex relaxations for other types of nonlinear terms.


  1. Li W, Hui CW, Li A. Integrating CDU, FCC and product blending models into refinery planning. Comput Chem Eng. 2005; 29(9): 2010-2028.
  2. Alhajri I, Elkamel A, Albahri T, Douglas PL. A nonlinear programming model for refinery planning and optimisation with rigorous process models and product quality specifications. Int J Oil Gas Coal Technol. 2008; 1(3): 283-307.
  3. Alattas AM, Grossmann IE, Palou-Rivera I. Refinery production planning: Multiperiod MINLP with nonlinear CDU model. Ind Eng Chem Res. 2012; 51(39): 12852-12861.
  4. Menezes BC, Kelly JD, Grossmann IE. Improved swing-cut modeling for planning and scheduling of oil-refinery distillation units. Ind Eng Chem Res. 2013; 52(51): 18324-18333.
  5. Fu G, Sanchez Y, Mahalec V. Hybrid model for optimization of crude oil distillation units. AIChE J. 2016; 62: 1065-1078.
  6. Li J, Boukouvala F, Xiao X, Floudas CA, Zhao B, Du G, Su X, Liu H. Data�driven mathematical modeling and global optimization framework for entire petrochemical planning operations. AIChE J. 2016. DOI: 10.1002/aic.15220
  7. Quesada I, Grossmann IE. Global optimization of bilinear process networks with multicomponent flows. Comput Chem Eng. 1995; 19(12): 1219-1242.
  8. Karuppiah R, Furman KC, Grossmann IE. Global optimization for scheduling refinery crude oil operations. Comput Chem Eng. 2008; 32(11): 2745-2766.
  9. Faria DC, Bagajewicz MJ. A new approach for global optimization of a class of MINLP problems with applications to water management and pooling problems. AIChE J. 2012; 58: 2320-2335.
  10. Yang Y, Barton PI. Refinery optimization Integrated with a nonlinear crude distillation unit model. IFAC-PapersOnLine. 2015; 48(8): 205-210.
  11. Castro PM. Normalized multiparametric disaggregation: An efficient relaxation for mixed-integer bilinear problems. J Glob Optim. 2016; 64(4): 765-784.
  12. McCormick GP. Computability of global solutions to factorable nonconvex programs: Part Iâ??Convex underestimating problems. Math Program. 1976; 10(1): 147-175.
  13. Tawarmalani M, Sahinidis NV. A polyhedral branch-and-cut approach to global optimization. Math Program. 2005; 103(2): 225-249.
  14. Misener R, Floudas CA. ANTIGONE: Algorithms for continuous/integer global optimization of nonlinear equations. J Glob Optim. 2014; 59(2-3): 503-526.