(564g) Decomposition Method for Mutiperiod Blending Scheduling

The efficient blending of liquid fuels and crude oils to meet both technical and environmental specifications has been a growing research area in recent years. The multiperiod blending problem seeks to maximize the profits associated with this process. Specifically, multiple liquid streams with various properties enter supply tanks. Then, they are fed into blending tanks where they are mixed in some proportion to meet a set of specifications. Finally, they are fed into demand tanks. The goal is then to select the flows that maximize the overall profit of the blending process. In the process, supply and demand may vary with time. Furthermore, operational constraints do not allow having flow coming in and going out of a blending tank simultaneously.

The modelling of this process makes use of binary variables to represent if there is flow between two tanks at any given time period, making the problem highly combinatorial. The description of the mixing constraints requires the use of bilinear terms, so global optimization tools are needed to find the optimal solution. These two issues make the mixed-integer nonlinear program (MINLP) difficult to solve.

Kolodziej et al.[1] use a discretization-based approach to solve the multiperiod blending problem to global optimality. The method used in their work discretizes some continuous variables with a certain precision, using the multiparametric disaggregation technique[2]. The algorithm they present shows good performance in comparison to commercial global optimization tools. The main downside is that it takes a long time to find feasible solutions in some cases. In practice, finding good feasible solutions fast is of utmost importance.

In this work we first present an alternative formulation to the multiperiod blending problem. This new formulation provides a structured problem that is easy to decompose. We then present a decomposition approach to the multiperiod blending problem. The proposed algorithm decomposes the MINLP model in two levels:  a master problem and a subproblem. The master problem is a mixed-integer linear program (MILP) relaxation of the original MINLP, obtained through the multiparametric disaggregation technique. This problem provides an upper bound to the MINLP. The subproblem is an MINLP in which a subset of discrete variables is fixed, yielding a reduction in the number of binary variables and bilinear terms. These problems are solved successively until the gap between the upper and lower bounds is closed.

For the solution of the MINLP we use a similar approach to the one presented by Kolodziej et al.[1]. This approach uses two MILP formulations derived from the multiparametric disaggregation technique. One of the MILPs is a relaxation; therefore, it provides an upper bound. The other MILP guarantees that, if a solution is found, then that solution is feasible for the original MINLP. The second MILP provides a lower bound. The algorithm starts by using a low precision discretization and solves both MILPs. If the gap between the upper bound and the lower bound is smaller than a specified parameter the algorithm stops. If it is larger, then the algorithm uses more precision in the discretization and solves the two MILPs again. This is repeated iteratively until the gap is smaller than the specified parameter.

We illustrate the performance of the algorithm with over 40 instances of the multiperiod blending problem. In general, the decomposition algorithm finds better solutions faster than the algorithm by Kolodziej et al.[1] and than commercial global optimization solvers. We also present a parallelization of the algorithm, showing the improvement in solution times.

[1] Kolodziej, S. P., Grossmann, I. E., Furman, K. C., and Sawaya, N. W. "A discretization-based approach for the optimization of the multiperiod blend scheduling problem." Computers & Chemical Engineering. 2013; 53, 122-142.

[2] Kolodziej, Scott, Pedro M. Castro, and Ignacio E. Grossmann. "Global optimization of bilinear programs with a multiparametric disaggregation technique." Journal of Global Optimization 2013; 57(4), 1039-1063.