A new relaxation technique based on fractional representation to solve bilinear models: Application to the long horizon crude oil scheduling problem

Document Type : Original Article

Authors

Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic), Iran

Abstract

This paper proposes a novel relaxation technique based on the fractional representation of bilinear terms. This technique is embedded into an iterative two-step MILP-NLP algorithm based on piecewise relaxation and domain reduction strategies. To evaluate the performance of the algorithm, it is compared to the recently addressed iterative MILP-NLP algorithm based on piecewise McCormick relaxation techniques over a variety of instances. Our method is also applied to the crude oil scheduling problem as an application. The results confirm the efficiency of the proposed algorithm from both solution quality and running time

Keywords

Main Subjects

References

[1] M. L. Bergamini, P. Aguirre, and I. Grossmann, Logic-based outer approximation for globally optimal synthesis of process networks, Computers & Chemical Engineering, 29 (2005), pp. 1914–1933.
[2] J. Bisschop, AIMMS - Optimization Modeling, 2012.
[3] P. M. Castro, Tightening piecewise mccormick relaxations for bilinear problems, Computers & Chemical Engineering, 72 (2015), pp. 300–311.
[4] P. M. Castro, Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problems, Journal of Global Optimization, 64 (2016), pp. 765–784.
[5] P. M. Castro and I. E. Grossmann, Global optimal scheduling of crude oil blending operations with RTN continuous-time and multiparametric disaggregation, Industrial & Engineering Chemistry Research, 53 (2014), pp. 15127–15145.
[6] P. M. Castro, I. E. Grossmann, and Q. Zhang, Expanding scope and computational challenges in process scheduling, Computers & Chemical Engineering, 114 (2018), pp. 14–42.
[7] J. Cerda, P. C. Pautasso, and D. C. Cafaro´ , Efficient approach for scheduling crude oil operations in marine-access refineries, Industrial & Engineering Chemistry Research, 54 (2015), pp. 8219–8238.
[8] X. Chen, S. Huang, D. Chen, Z. Zhang, L. Zheng, I. Grossmann, and S. Chen, Hierarchical decomposition approach for crude oil scheduling: A sinopec case, Interfaces, 44 (2014), pp. 269–285.
[9] G. Corsano, A. R. Vecchietti, and J. M. Montagna, Optimal design for sustainable bioethanol supply chain considering detailed plant performance model, Computers & Chemical Engineering, 35 (2011), pp. 1384– 1398. Energy & Sustainability.
[10] R. Dai, H. Charkhgard, and F. Rigterink, A robust biobjective optimization approach for operating a shared energy storage under price uncertainty, International Transactions in Operational Research, 29 (2022), pp. 1627–1658.
[11] L. S. de Assis, E. Camponogara, B. Zimberg, E. Ferreira, and I. E. Grossmann, A piecewise
McCormick relaxation-based strategy for scheduling operations in a crude oil terminal, Computers & Chemical Engineering, 106 (2017), pp. 309–321. ESCAPE-26.
[12] S. S. Dey, A. Santana, and Y. Wang, New SOCP relaxation and branching rule for bipartite bilinear programs, Optimization and Engineering, 20 (2019), pp. 307–336.
[13] C. D’Ambrosio, A. Lodi, and S. Martello, Piecewise linear approximation of functions of two variables in milp models, Operations Research Letters, 38 (2010), pp. 39–46.
[14] F. Evazabadian, M. Arvan, and R. Ghodsi, Short-term crude oil scheduling with preventive maintenance operations: a fuzzy stochastic programming approach, International Transactions in Operational Research, 26 (2019), pp. 2450–2475.
[15] M. Fampa and W. Pimentel, Linear programing relaxations for a strategic pricing problem in electricity markets, International Transactions in Operational Research, 24 (2017), pp. 159–172.
[16] D. C. Faria and M. J. Bagajewicz, A new approach for global optimization of a class of minlp problems with applications to water management and pooling problems, AIChE Journal, 58 (2012), pp. 2320–2335.
[17] M. Fischetti and M. Monaci, A branch-and-cut algorithm for mixed-integer bilinear programming, European Journal of Operational Research, 282 (2020), pp. 506–514.
[18] L. R. Foulds, D. Haugland, and K. Jornsten¨ , A bilinear approach to the pooling problem†, Optimization, 24 (1992), pp. 165–180.
[19] A. Gupte, S. Ahmed, M. S. Cheon, and S. Dey, Solving mixed integer bilinear problems using MILP formulations, SIAM Journal on Optimization, 23 (2013), pp. 721–744.
[20] M. M. F. Hasan and I. Karimi, Piecewise linear relaxation of bilinear programs using bivariate partitioning, AIChE Journal, 56 (2010), pp. 1880–1893.
[21] D. W. Holland and J. L. Baritelle, School consolidation in sparsely populated rural areas: A separable programming approach, American Journal of Agricultural Economics, 57 (1975), pp. 567–575.
[22] F. Hooshmand, M. Jamalian, and S. A. MirHassani, Efficient two-phase algorithm to solve nonconvex minlp model of pump scheduling problem, Journal of Water Resources Planning and Management, 147 (2021), p. 04021047.
[23] R. Karuppiah, K. C. Furman, and I. E. Grossmann, Global optimization for scheduling refinery crude oil operations, Computers & Chemical Engineering, 32 (2008), pp. 2745–2766. Enterprise-Wide Optimization.
[24] T. Kleinert, V. Grimm, and M. Schmidt, Outer approximation for global optimization of mixed-integer quadratic bilevel problems, Mathematical Programming, 188 (2021), pp. 461–521.
[25] H. Lee, J. M. Pinto, I. E. Grossmann, and S. Park, Mixed-integer linear programming model for refinery short-term scheduling of crude oil unloading with inventory management, Industrial & Engineering Chemistry Research, 35 (1996), pp. 1630–1641.
[26] L. Liberti, S. Cafieri, and F. Tarissan, Reformulations in Mathematical Programming: A Computational Approach, Springer Berlin Heidelberg, Berlin, Heidelberg, 2009, pp. 153–234.
[27] G. P. McCormick, Computability of global solutions to factorable nonconvex programs: Part i — convex underestimating problems, Mathematical Programming, 10 (1976), pp. 147–175.
[28] M. Mikolajkova, H. Sax´ en, and F. Pettersson´ , Linearization of an minlp model and its application to gas distribution optimization, Energy, 146 (2018), pp. 156–168. Process Integration for Energy Saving and Pollution Reduction – PRES 2016.
[29] S. Mouret, I. E. Grossmann, and P. Pestiaux, A new lagrangian decomposition approach applied to the integration of refinery planning and crude-oil scheduling, Computers & Chemical Engineering, 35 (2011), pp. 2750–2766.
[30] H. Nagarajan, M. Lu, S. Wang, R. Bent, and K. Sundar, An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs, Journal of Global Optimization, 74 (2019), pp. 639– 675.
[31] A. d. L. Stanzani, V. Pureza, R. Morabito, B. J. V. d. Silva, D. Yamashita, and P. C. Ribas,
Optimizing multiship routing and scheduling with constraints on inventory levels in a brazilian oil company, International Transactions in Operational Research, 25 (2018), pp. 1163–1198.
[32] J. P. Teles, P. M. Castro, and H. A. Matos, Multi-parametric disaggregation technique for global optimization of polynomial programming problems, Journal of Global Optimization, 55 (2013), pp. 227–251.
[33] , Univariate parameterization for global optimization of mixed-integer polynomial problems, European Journal of Operational Research, 229 (2013), pp. 613–625.
AUT Journal of Mathematics and Computing
Volume 6, Issue 2
March 2025
Pages 121-142

Files

Share

How to cite

Statistics