A new robust counterpart model for uncertain linear programming problems

Subject Areas : Mathematical Optimization

Hamid Amiri ¹ , Rasoul Shafaei ²

1 - Department of Industrial Engineering, K.N. Toosi University of Technology, Tehran, Iran
2 - Department of Industrial Engineering, K.N. Toosi University of Technology, Tehran, Iran

Received: 2022-05-07 Accepted : 2023-02-26 Published : 2022-06-01

Keywords: perturbation variables, robust counterpart optimization, uncertain coefficients, uncertainty set‎,

Abstract :

Many practical decision-making problems involve a significant level of data uncertainty. In such a case, modeling the uncertainty involved is critical to making informed decisions. The set-based robust optimization approach is one of the most efficient techniques for finding optimal decisions in problems involving uncertain data. The main concern with this technique is over-conservatism. This drawback has been widely investigated, and several robust formulations have been developed in the literature to deal with it. However, research is still ongoing to obtain effective formulations to handle uncertainty. In this study, we derive a robust counterpart formulation for an uncertain linear programming problem under a new uncertainty set that is defined based on a pairwise comparison of perturbation variables. The performance of the proposed robust formulation is evaluated using numerical studies and in terms of different performance metrics. For this purpose, robust counterpart models corresponding to the production-mix sample problems are solved at different protection levels. Then, for each solution obtained, violation probability is calculated using a Monte-Carlo simulation approach. The results revealed that the proposed method outperforms the existing ones.

References:

[1] Li, Z., Ding, R., & Floudas, C. A. (2011). A comparative theoretical and computational study on robust counterpart optimization: I. Robust linear optimization and robust mixed integer linear optimization. Industrial & Engineering Chemistry Research, 50(18), 10567–10603. https://doi.org/10.1021/ie200150p.

[2] Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). Robust optimization. Princeton university press. https://doi.org/10.1016/s1474-6670(17)42591-2.

[3] Baringo, A., & Baringo, L. (2016). A stochastic adaptive robust optimization approach for the offering strategy of a virtual power plant. IEEE Transactions on Power Systems, 32(5),3492–3504. https://doi.org/10.1109/TPWRS.2016.2633546.

[4] Taghizadeh, M., Bahramara, S., Adabi, F., & Nojavan, S. (2020). Optimal thermal and electrical operation of the hybrid energy system using interval optimization approach. Applied Thermal Engineering, 169, 114993. https://doi.org/10.1016/j.applthermaleng.2020.114993.

[5] Yu, D., Zhang, T., He, G., Nojavan, S., Jermsittiparsert, K., & Ghadimi, N. (2020). Energy management of wind-PV-storage-grid based large electricity consumer using robust optimization technique. Journal of Energy Storage, 27, 101054. https://doi.org/10.1016/j.est.2019.101054.

[6] Cao, Y., Huang, L., Li, Y., Jermsittiparsert, K., Ahmadi-Nezamabad, H., & Nojavan, S. (2020). Optimal scheduling of electric vehicles aggregator under market price uncertainty using robust optimization technique. International Journal of Electrical Power and Energy Systems, 117, 105628. https://doi.org/10.1016/j.ijepes.2019.105628.

[7] Luo, Y., Wang, Z., Zhu, J., Lu, T., Xiao, G., Chu, F., & Wang, R. (2022). Multi-objective robust optimization of a solar power tower plant under uncertainty. Energy, 238, 121716. https://doi.org/10.1016/j.energy.2021.121716.
[8] Yu, D., Wu, J., Wang, W., & Gu, B. (2022). Optimal performance of hybrid energy system in the presence of electrical and heat storage systems under uncertainties using stochastic p-robust optimization technique. Sustainable Cities and Society, 83, 103935. https://doi.org/10.1016/j.scs.2022.103935.
[9] Parvar, S. S., & Nazaripouya, H. (2022). Optimal Operation of Battery Energy Storage Under Uncertainty Using Data-Driven Distributionally Robust Optimization. Electric Power Systems Research, 211, 108180. https://doi.org/10.1016/j.epsr.2022.108180.
[10] Righetto, G. M., Morabito, R., & Alem, D. (2016). A robust optimization approach for cash flow management in stationery companies. Computers & Industrial Engineering, 99, 137–152. https://doi.org/10.1016/j.cie.2016.07.010.
[11] Ashrafi, H., & Thiele, A. C. (2021). A study of robust portfolio optimization with European options using polyhedral uncertainty sets. Operations Research Perspectives, 8, 100178. https://doi.org/10.1016/j.orp.2021.100178.
[12] Aalaei, A., & Davoudpour, H. (2017). A robust optimization model for cellular manufacturing system into supply chain management. International Journal of Production Economics, 183, 667–679. https://doi.org/10.1016/j.ijpe.2016.01.014.
[13] Bairamzadeh, S., Saidi-Mehrabad, M., & Pishvaee, M. S. (2018). Modelling different types of uncertainty in biofuel supply network design and planning: A robust optimization approach. Renewable Energy, 116, 500–517. https://doi.org/10.1016/j.renene.2017.09.020.
[14] Thevenin, S., Ben-Ammar, O., & Brahimi, N. (2022). Robust optimization approaches for purchase planning with supplier selection under lead time uncertainty. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2022.03.029.
[15] Krishnan, R., Arshinder, K., & Agarwal, R. (2022). Robust optimization of sustainable food supply chain network considering food waste valorization and supply uncertainty. Computers & Industrial Engineering, 171, 108499.
[16] Chen, L., Gendreau, M., Hà, M. H., & Langevin, A. (2016). A robust optimization approach for the road network daily maintenance routing problem with uncertain service time. Transportation Research Part E: Logistics and Transportation Review, 85, 40–51. https://doi.org/10.1016/j.tre.2015.11.006.
[17] Ziaei, Z., & Jabbarzadeh, A. (2021). A multi-objective robust optimization approach for green location-routing planning of multi-modal transportation systems under uncertainty. Journal of Cleaner Production, 291, 125293. https://doi.org/10.1016/j.jclepro.2020.125293.
[18] Banerjee, O., El Ghaoui, L., & d’Aspremont, A. (2008). Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data. The Journal of Machine Learning Research, 9, 485–516. https://doi.org/10.1145/1390681.1390696.
[19] Candès, E. J., Li, X., Ma, Y., & Wright, J. (2011). Robust principal component analysis? Journal of the ACM (JACM), 58(3), 1–37. https://doi.org/10.1145/1970392.1970395.
[20] Xu, H., Caramanis, C., & Mannor, S. (2010). Robust regression and lasso. IEEE Transactions on Information Theory, 56(7), 3561–3574. https://doi.org/10.1109/TIT.2010.2048503.
[21] Xu, H., Caramanis, C., & Mannor, S. (2009). Robustness and Regularization of Support Vector Machines. Journal of Machine Learning Research, 10(7).
[22] Wang, C., Peng, X., Shang, C., Fan, C., Zhao, L., & Zhong, W. (2021). A deep learning-based robust optimization approach for refinery planning under uncertainty. Computers and Chemical Engineering, 155, 107495. https://doi.org/10.1016/j.compchemeng.2021.107495.
[23] Singh, S., & Biswal, M. P. (2021). A robust optimization model under uncertain environment: An application in production planning. Computers and Industrial Engineering, 155, 107169. https://doi.org/10.1016/j.cie.2021.107169.
[24] Zhang, L., Yuan, Z., & Chen, B. (2022). Adjustable Robust Optimization for the Multi-period Planning Operations of an Integrated RefineryPetrochemical Site under Uncertainty. Computers and Chemical Engineering, 160, 107703. https://doi.org/10.1016/j.compchemeng.2022.107703
[25] Soyster, A. L. (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations Research, 21(5), 1154–1157. https://doi.org/10.1287/opre.21.5.1154.
[26] El Ghaoui, L., & Lebret, H. (1997). Robust solutions to least-squares problems with uncertain data. SIAM Journal on Matrix Analysis and Applications, 18(4), 1035–1064. https://doi.org/10.1137/S0895479896298130.
[27] El Ghaoui, L., Oustry, F., & Lebret, H. (1998). Robust solutions to uncertain semidefinite programs. SIAM Journal on Optimization, 9(1), 33–52. https://doi.org/10.1137/S1052623496305717.
[28] Ben-Tal, A., & Nemirovski, A. (1998). Robust convex optimization. Mathematics of Operations Research, 23(4), 769–805. https://doi.org/10.1287/moor.23.4.769.
[29] Ben-Tal, A., & Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–13. https://doi.org/10.1016/S0167-6377(99)00016-4.

[30] Ben-Tal, A., & Nemirovski, A. (2000). Robust solutions of linear programming problems contaminated with uncertain data. Mathematical Programming, 88(3), 411–424. https://doi.org/10.1007/PL00011380.
[31] Bertsimas, D., & Sim, M. (2003). Robust discrete optimization and network flows. Mathematical Programming, 98(1), 49–71. https://doi.org/10.1007/s10107-003-0396-4.
[32] Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53. https://doi.org/10.1287/opre.1030.0065.
[33] Mulvey, J. M., Vanderbei, R. J., & Zenios, S. A. (1995). Robust optimization of large-scale systems. Operations Research, 43(2), 264–281. https://doi.org/10.1287/opre.43.2.264.
[34] Pachamanova, D. A. (2002). A robust optimization approach to finance. Massachusetts Institute of Technology.
[35] Jalilvand-Nejad, A., Shafaei, R., & Shahriari, H. (2016). Robust optimization under correlated polyhedral uncertainty set. Computers & Industrial Engineering, 92, 82–94. https://doi.org/10.1016/j.cie.2015.12.006.
[36] Daneshvari, H., & Shafaei, R. (2021). A new correlated polyhedral uncertainty set for robust optimization. Computers & Industrial Engineering, 157, 107346. https://doi.org/10.1016/j.cie.2021.107346