An improved three-step method for solving the interval linear programming problems. (English) Zbl 1460.65064
Summary: Feasibility condition, which ensures that the solution space does not violate any constraints, and optimality condition, which guarantees that all points of the solution space are optimal, are very significant conditions for the solution space of interval linear programming (ILP) problems. Among the existing methods for ILP problems, the best-worst cases (BWC) method and two-step method (TSM) do not ensure feasibility condition, while the modified ILP (MILP), robust TSM (RTSM), improved TSM (ITSM), and three-step method (ThSM) guarantee feasibility condition, whose solution spaces may not be completely optimal. We propose an improved ThSM (IThSM) for ILP problems, which ensures both feasibility and optimality conditions, i.e., we introduce an extra step to optimality.
Keywords:
feasibility; interval linear programming; optimality; robust two-step method; three-step methodReferences:
| [1] | Alefeld, G., Herzberger, J.,Introduction to Interval Computations, Academic Press, New York, 1983. · Zbl 0552.65041 |
| [2] | Allahdadi, M., Mishmast Nehi, H., “The optimal solutions set of the interval linear programming problems”,Optimization Letters, 7 (2013) 893-1911. · Zbl 1311.90069 |
| [3] | Allahdadi, M., Mishmast Nehi, H., Ashayerinasab, H. A., Javanmard, M., “Improving the modified interval linear programming method by new techniques”,Information Sciences, 339 (2016) 224-236. |
| [4] | Ashayerinasab, H. A., Mishmast Nehi, H., Allahdadi, M., “Solving the interval linear programming problem: A new algorithm for a general case”,Expert Systems With Applications, 93 (2018) 39-49. |
| [5] | Beeck, H., “Linear programming with inexact data”, Technical report TUM-ISU-7830, Technical University of Munich, Munich, 1978. |
| [6] | Chinneck, J.W., Ramadan, K., “Linear programming with interval coefficients”,Journal of the Operational Research Society, 51 (2000) 209-220. · Zbl 1107.90420 |
| [7] | Fan, Y.R., Huang, G.H., “A robust two-step method for solving interval linear programming problems within an environmental management context”,Journal of Environmental Informatics, 19 (1) (2012) 1-9. |
| [8] | Hansen, H., Walster, G. W.,Global Optimization Using Interval Analysis, Second Edition, Revised and Expanded, Dekker, New York, 1992. · Zbl 0762.90069 |
| [9] | Hladik, M., “How to determine basis stability in interval linear programming”,Optim. Lett., 8 (2014) 375-389. · Zbl 1288.90047 |
| [10] | Hladik, M., “Interval linear programming: A survey”, in: Z. A. Mann, editor, Linear Programming, New Frontiers in Theory and Applications, Nova Science Publishers, New York, 2012 (2) 85-120. |
| [11] | Huang, G.H., Baetz, B.W., Patry, G.G., “A grey linear programming approach for municipal solid waste management planning under uncertainty”,Civ. Eng. Environ. Syst., 9 (1992) 319-335. |
| [12] | Huang, G.H., Baetz, B.W., Patry, G.G., “Grey integer programming: an application to waste management planning under uncertainty”,Eur. J. Oper. Res., 83 (1995) 594-620. · Zbl 0899.90131 |
| [13] | Huang, G.H., Cao, M.F., “Analysis of solution methods for interval linear programming”, Journal of Environmental Informatics, 17 (2) (2011) 54-64. |
| [14] | Huang, G.H., Moore, R.D., “Grey linear programming, its solving approach, and its application”,International Journal of Systems Science, 24 (1993) 159-172. · Zbl 0772.90060 |
| [15] | Jansson, C., “A self-validating method for solving linear programming problems with interval input data”, in: Kulisch, U., Stetter, H.J. (eds.) Scientific computation with automatic result verification, Computing Suppl., 6 (1988) 33-45. · Zbl 0661.65056 |
| [16] | Jansson, C., Rump, S. M., “Rigorous solution of linear programming problems with uncertain data”,Oper. Res., 35 (2) (1991) 87-111. · Zbl 0735.90043 |
| [17] | Konickova, J., “Sufficient condition of basis stability of an interval linear programming problem”,ZAMM. Z. Angew. Math. Mech., 81 (3) (2001) 677-678. · Zbl 0983.90037 |
| [18] | Li, Y.P., Huang, G. H., Guo, p., Yang, Z. F., and Nie, S. L., “A dual-interval vertex analysis method and its application to environmental decision making under uncertainty”,Eur. J. Oper. Res., 200 (2010) 536-550. · Zbl 1177.90433 |
| [19] | Machost, B., “Numerische Behandlung des Simplexverfahrens mit intervallanalytischen Methoden”, Tech. Rep. 30, Berichte der Gesellschaft fr Mathematik und Datenverarbeitung, 54 pages, Bonn, 1970. · Zbl 0204.49404 |
| [20] | Mraz, F., “On infimum of optimal objective function values in interval linear programming”, Technical report KAM Series, Department of Applied Mathematics, Charles University, Prague, 96-337,1996. |
| [21] | Rex, J., Rohn, J., “Sufficient conditions for regularity and singularity of interval matrices”, SIAM J. Matrix Anal. Appl., 20 (2) (1998) 437-445. · Zbl 0924.15003 |
| [22] | Rohn, J., “Cheap and tight bound: The recent result by E. Hansen can be made more efficient”,Interval comput., 4 (1993) 13-21. · Zbl 0830.65019 |
| [23] | Rohn, J., “Forty necessary and sufficient conditions for regularity of interval matrices: A survey”,J. Linear Algebra, 18 (2009) 500-512. · Zbl 1189.65088 |
| [24] | Rohn, J.,“Interval linear programming”, in M. Fiedler et al., editor,Linear optimization problems with inexact data, chapter 3, pages 79-100, Springer, New York, 2006. · Zbl 1106.90051 |
| [25] | Rohn, J., “Stability of the optimal basis of a linear program under uncertainty”,Oper. Res. Lett., 13 (1) (1993) 9-12. · Zbl 0777.90029 |
| [26] | Tong, S.C., “Interval number, fuzzy number linear programming”,Fuzzy Sets and Systems, 66 (1994) 301-306. |
| [27] | Wang, X., Huang, G., “Violation analysis on two-step method for interval linear programming”,Information Sciences, 281 (2014) 85-96. · Zbl 1355.90046 |
| [28] | Zhou, F., Huang, G. H., Chen, G., Guo, H., “Enhanced-interval linear programming”, European Journal of Operational Research, 199 (2009) 323-333. · Zbl 1176.90407 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
