Skip to main content
SpringerLink
Log in

Checking weak optimality of the solution to linear programming with interval right-hand side

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

The interval linear programming (IvLP) is a method for decision making under uncertainty. A weak feasible solution to IvLP is called weakly optimal if it is optimal for some scenario of the IvLP. One of the basic and difficult tasks in IvLP is to check whether a given point is weak optimal. In this paper, we investigate linear programming problems with interval right-hand side. Some necessary and sufficient conditions for checking weak optimality of given feasible solutions are established, based on the KKT conditions of linear programming. The proposed methods are simple, easy to implement yet very effective, since they run in polynomial time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Chinneck, J.W., Ramadan, K.: Linear programming with interval coefficients. J. Oper. Res. Soc. 51(2), 209–220 (2000)

    Google Scholar 

  2. Fiedler, M., Nedoma, J., Ramik, J., Rohn, J., Zimmermann, K.: Linear optimization problems within exact data. Springer-Verlag, New York (2006)

    Google Scholar 

  3. Liu, S.-T., Wang, R.-T.: A numerical solution method to interval quadratic programming. Appl. Math. Comput. 189, 1274–1281 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  4. Li, W., Tian, X.: Numerical solution method for general interval quadratic programming. Appl. Math. Comput. 202, 589–595 (2008)

    Google Scholar 

  5. Li, W., Tian, X.: Fault detection in discrete dynamic systems with uncertainty based on interval optimization. Math. Model. Anal. 16(4), 549–557 (2011)

    Google Scholar 

  6. Hladík, M.: Optimal value range in interval linear programming. Fuzzy Optim. Decis. Mak. 8(3), 283–294 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  7. Hladík, M.: Interval linear programming: a survey. In: Adam Mann, Z (ed.) Linear Programming New Frontiers. Nova Science Publishers Inc, Nova (2011)

  8. Hladík, M.: Optimal value bounds in nonlinear programming with interval data. TOP 19(1), 93–106 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  9. Virgini, G., Cecile, M., Nabila, R.: Linear programming with interval right hand sides. Int. Trans. Oper. Res. 17(3), 397–408 (2010)

    Article  MathSciNet  Google Scholar 

  10. Ralph, E.: Steuer, algorithms for linear programming problems with interval objective function coefficients. Math. Oper. Res. 6, 333–348 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  11. Ishibuchi, H., Tanaka, H.: Multiobjective programming in optimization of the interval objective function. Eur. J. Oper. Res. 48, 219–225 (1990)

    Article  MATH  Google Scholar 

  12. Moore, R.E., Kearfott, R.B., Cloud, M.J.: Introduction to interval analysis. SIAM, Philadelphia (2009)

    Book  MATH  Google Scholar 

  13. Alefeld, G., Herzberger, J.: Introduction to interval computations. Academic Press, NewYork (1983)

    MATH  Google Scholar 

  14. Neumaier, A.: Interval methods for systems of equations. Cambridge University Press, Cambridge (1990)

    MATH  Google Scholar 

  15. Rohn, J., Kreslová, J.: Linear interval inequalities. Linear Multilinear Algebra 38, 79–82 (1994)

    Article  MATH  Google Scholar 

  16. Rohn, J.: An algorithm for computing the hull of the solution set of interval linear equations. Linear Algebra Appl. 435, 193–201 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  17. Rohn, J.: A general method for enclosing solutions of interval linear equations. Optim. Lett. 6, 709–717 (2012). doi:10.1007/s11590-011-0296-0

    Google Scholar 

  18. Shary, S.P.: A new technique in systems analysis under interval uncertainty and ambiguity. Reliab. Comput. 8(5), 321–418 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  19. Shary, S.P.: Solving the interval linear tolerance problem. Math. Comput. Simul. 39, 53–85 (1995)

    Article  MathSciNet  Google Scholar 

  20. Prokopyev, O.A., Butenko, S., Trapp, A.: Checking solvability of systems of interval linear equations and inequalities via mixed integer programming. Eur. J. Oper. Res. 199, 117–121 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  21. Alefeld, G., Kreinovich, V., Mayer, G.: On the solution sets of particular classes of linear interval systems. J. Comput. Appl. Math. 152, 1–15 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  22. Li, W., Wang, H., Wang, Q.: Localized solutions to interval linear equations. J. Comput. Appl. Math. 238, 29–38 (2013)

    Google Scholar 

  23. Allahdadi, M., Mishmast Nehi, H.: The optimal solution set of the interval linear programming problems. Optim. Lett. doi:10.1007/s11590-012-0530-4

  24. Hladík, M.: How to determine basis stability in interval linear programming. Optim. Lett. doi:10.1007/s11590-012-0589-y

Download references

Acknowledgments

The authors are grateful to the editor and both the anonymous referees for their constructive comments and suggestions, which have improved the presentation of this paper. This project was supported by the National Natural Science Foundation of China (Grant No. 61003194, 11171316) and PPKC2013YB011.

Author information

Authors and Affiliations

  1. Institute of Operational Research & Cybernetics, Hangzhou Dianzi University, Hangzhou,  310018, People’s Republic of China

    Wei Li, Jiajia Luo & Ya Li

  2. College of Science, China Jiliang University, Hangzhou,  310018, People’s Republic of China

    Qin Wang

Authors
  1. Wei Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jiajia Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Qin Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ya Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wei Li.

Additional information

We use abbreviation Ivlp, instead of ILP, for interval linear programming, to avoid confusion with the abbreviation for integer linear programming.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Li, W., Luo, J., Wang, Q. et al. Checking weak optimality of the solution to linear programming with interval right-hand side. Optim Lett 8, 1287–1299 (2014). https://doi.org/10.1007/s11590-013-0654-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-013-0654-1

Keywords

Search

Navigation