An improved three-step method for solving the interval linear programming problems

Authors

  • Mehdi Allahdadi University of Sistan and Baluchestan, Mathematics Faculty, Zahedan, Iran
  • Chongyang Deng Hangzhou Dianzi University, School of Science, Hangzhou, PR China

DOI:

https://doi.org/10.2298/YJOR180117020A

Keywords:

Feasibility, Interval Linear Programming, Optimality, Robust two-step Method, Three-step Method

Abstract

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.

References

Alefeld, G., Herzberger, J., Introduction to Interval Computations, Academic Press, New York, 1983.

Allahdadi, M., Mishmast Nehi, H., The optimal solutions set of the interval linear programming problems, Optimization Letters, 7 (2013) 893-1911.

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.

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.

Beeck, H., Linear programming with inexact data, Technical report TUM-ISU-7830, Technical University of Munich, Munich, 1978.

Chinneck, J.W., Ramadan, K., Linear programming with interval coefficients, Journal of the Operational Research Society, 51 (2000) 209-220.

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.

Hansen, H., Walster, G. W., Global Optimization Using Interval Analysis, Second Edition, Revised and Expanded, Dekker, New York, 1992.

Hladik, M., How to determine basis stability in interval linear programming, Optim. Lett., 8 (2014) 375-389.

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.

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.

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.

Huang, G.H., Cao, M.F., Analysis of solution methods for interval linear programming, Journal of Environmental Informatics, 17 (2) (2011) 54-64.

Huang, G.H., Moore, R.D., Grey linear programming, its solving approach, and its application, International Journal of Systems Science, 24 (1993) 159-172.

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.

Jansson, C., Rump, S. M., Rigorous solution of linear programming problems with uncertain data, Oper. Res., 35 (2) (1991) 87-111.

Konickova, J., Sufficient condition of basis stability of an interval linear programming problem, ZAMM. Z. Angew. Math. Mech., 81 (3) (2001) 677-678.

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.

Machost, B., Numerische Behandlung des Simplexverfahrens mit intervallanalytischen Methoden, Tech. Rep. 30, Berichte der Gesellschaft für Mathematik und Datenverarbeitung, 54 pages, Bonn, 1970.

Mraz, F., On inmum of optimal objective function values in interval linear programming, Technical report KAM Series, Department of Applied Mathematics, Charles University, Prague, 96-337, 1996.

Rex, J., Rohn, J., Sufficient conditions for regularity and singularity of interval matrices, SIAM J. Matrix Anal. Appl., 20 (2) (1998) 437-445.

Rohn, J., Cheap and tight bound: The recent result by E. Hansen can be made more efficient, Interval Comput., 4 (1993) 13-21.

Rohn, J., Forty necessary and sufficient conditions for regularity of interval matrices: A survey, J. Linear Algebra, 18 (2009) 500-512.

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.

Rohn, J., Stability of the optimal basis of a linear program under uncertainty, Oper. Res. Lett., 13 (1) (1993) 9-12.

Tong, S.C., Interval number, fuzzy number linear programming, Fuzzy Sets and Systems, 66 (1994) 301-306.

Wang, X., Huang, G., Violation analysis on two-step method for interval linear programming, Information Sciences, 281 (2014) 85-96.

Zhou, F., Huang, G. H., Chen, G., Guo, H., Enhanced-interval linear programming, European Journal of Operational Research, 199 (2009) 323-333.

Downloads

Published

2018-11-01

Issue

Vol. 28 No. 4 (2018)

Section

Research Articles

License

Copyright (c) 2018 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.