An updated two-step method for solving interval linear programming: A case study of the air quality management problem

Document Type : Research Article


University of Sistan and Baluchestan


Many real-world problems occur under uncertainty. In this paper, we consider interval linear programming (ILP) which can be used to tackle un certainties. Several methods have been proposed by researchers, such as the best and worst cases, Two-step method (TSM), improved TSM, ILP, improved ILP, three-step method, and robust two-step method. First, we define feasibility and optimality conditions in ILP models and review some solving methods shortly, and then show that some solutions of the TSM method are not feasible. Therefore, we propose an updated TSM method (namely, UTSM) by considering the feasibility and optimality conditions. In this paper, the UTSM method was applied to identify the reduction of aerosols by using two controllers with a minimized cost to demonstrate its application under uncertainty. Compared with other methods, the solutions obtained through ILP were presented as interval, which can provide intervals for the decision variables, objective function, and decision-makers. Therefore, the decision-makers can make the best decision based on the obtained solutionsthrough ILP, and then identify desired plans for aerosol-emission control under uncertainty.


1. Alefeld, G. and Herzberger, J. Introduction to interval computations. Academic Press, New York, 1983.
2. Allahdadi, M. and Deng, C.An improved three-step method for solving the interval linear programming problem, Yugoslav J. Oper. Res. 28 (4) (2018), 435–451.
3. Allahdadi, M. and MishmastNehi H. The optimal solution set of the interval linear programming problems, Optim. Lett. 7(2013), 893–1911.
4. Allahdadi, M., MishmastNehi, H. Ashayerinasab, H.A. and Javanmard, M. Improving the modified interval linear programming method by new techniques. Inf. Sci. 339 (2016), 224–236.
5. Ashayerinasab, H. A., Mishmast Nehi, H. and Allahdadi, M. Solving the interval linear programming problem: A new algorithm for a general case, Expert Sys. Appl. 93 (2018), 1, 39–49.
6. Atmospheric dust (2009), Comet Program, /comet/mesoprim/at dust/print.htm.
7. Chinneck, J. W. and Ramadan, K. Linear programming with interval coefficients J. Oper. Res. Soc. 51 (2000), 209–220.
8. Davidson, G.A. A modified power law representation of the pasquuill gif ford dispersion coefficients J. Air Waste Manage. Assoc. 40 (1990), 1146–1147.
9. Engelstaedter. S, Tegen. I, and Washington. R. North African dust emissions and transport, Earth-Sci. Rev. 79 (2006), 73–100.
10. Fan, Y.R., and Huang, G.H. A robust two-step method for solving in terval linear programming problems within an environmental management context, J. Environ. Inform. 19 (1) (2012), 1–9.
11. Fan, Y., Huang, G. and Veawab, A. A generalized fuzzy linear program ming approach for environmental management problem under uncertainty, J. Air Waste Manage. Assoc. 62(1) (2011), 72–86.
12. Garajova, E., Hladk, M. and Rada, M. The effects of transformations on the optimal set in interval linear programming, In Proceedings of the 14th International Symposium on Operational Research, SOR17, Bled, Slovenian Society Informatika, Ljubljana, Slovenia, (2017), 487–492.
13. Goudie A.S. and Middleton N.J. desert dust in the global system, Springer Berlin Heidelberg , Berlin (2006).
14. Haith, A.D. Environmental systems optimization. John Wiley & Sons, New York, 1982.
15. Hladk, M. How to determine basis stability in interval linear programming, Optim.Lett. 8 (2014), 375–389.
16. Huang, G.H., Baetz, B.W. and Patry, G.G. A gray integer programming: an application to waste management planning under uncertainty, Eur. J. Oper. Res. 83 (1995), 594–620.
17. Huang, G.H. and Cao, M.F. Analysis of solution methods for interval linear programming, J. Environ. Inform. 17 (2) (2011), 54–64.
18. Huang, G.H. and Moore, R.D. Grey linear programming, its solving approach, and its application, Int. J. Sys. Sci. 24 (1993), 159–172.
19. Islam, M.N., Rahman, K.S., Bahar, M.M., Habib, M.A., Ando, K. and Hattori, N. Pollution attenuation by roadside green belt in and around urban areas, Urban For. Urban Gree. (2012), 460–464.
20. Li, Y.P., Huang, G.H., Guo, P., Yang, Z.F. and Nie S. A dual-interval vertex analysis method and its application to environmental decision making under uncertainty. Eur. J. Oper. Res. 200 (2010), 536–550.
21. Nowak, D.J., Crane, D.E., and Stevens, J.C. Air pollution removal by urban trees and shrubs in the United States, Urban For. Urban Gree. 4 (2006), 115–123.
22. Nowak, J., Hirabayashi. S., Bodine. A. and Hoehn. R. Modeled PM2.5 removal by trees in ten U.S. cities and associated health effects, Environ. Pollut. 178 (2013), 395–402.
23. Pasguill, F.S. Atmospheric diffusion. third edition. Ellis Horwood Limited, Publishers Chichester, 1983.
24. Rashki, A. Seasonality and mineral, chemical and optical properties of dust storms in the Sistan region of Iran and their influence on human health. Faculty of natural and agricultural sciences university of Pretoria, PhD thesis, 2012.
25. Rashki, A., Kaskaoutis, D.G., Francois, P., Kosmopoulos, P.G. and Legrand, M. Dust storms and their horizontal dust loading in the Sistanregion, Iran. Aeolian Res. 5 (2012), 51–62
26. Rashki, A., Kaskaoutis, D.G., Rautenbach C.J. de W., Eriksson, P.G., M. Qiang, M. and Gupta, P. Dust storms and their horizontal dust loading in the Sistan region, Iran: seasonality, transport characteristics and affected areas. Aeolian Res. 16 (2015), 35–48.
27. Rex, J. and Rohn, J. Sufficient conditions for regularity and singularity of interval matrices, SIAM J. Matrix Anal. Appl. 20 (2) (1998), 437–445.
28. Rohn, J. Cheap and tight bound: The recent result by E. Hansen can be made more efficient, Interval Comput. 4(1993),13–21.
29. Rohn, J. Forty necessary and sufficient conditions for regularity of interval matrices: A survey, Electron. J. Linear Algebra 18 (2009), 500–512.
30. Tong, S.C. Interval number, fuzzy number linear programming. Fuzzy Sets Syst., 66 (1994), 301–306.
31. Wang, X. and Huang, G. Violation analysis on two-step method for in terval linear programming Inf. Sci. 281 (2014), 85–96.
32. Xuan, J., Sokolik, I.N., Hao, J., Guo., F., Mao, H. and Yang, G. Identification and characterization of sources of atmospheric mineral dust in east Asia, Atmos. Environ. 38(36) (2004), 6239–6252.
33. Zhou, F., Huang, G.H., Chen, G. and Guo, H. Enhanced interval linear programming, Eur. J. Oper. Res. 199 (2009), 323–333.