Skip to main content
SpringerLink
Log in

Complexity of necessary efficiency in interval linear programming and multiobjective linear programming

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

Abstract

We present some complexity results on checking necessary efficiency in interval multiobjective linear programming. Supposing that objective function coefficients perturb within prescribed intervals, a feasible point x* is called necessarily efficient if it is efficient for all instances of interval data. We show that the problem of checking necessary efficiency is co-NP-complete even for the case of only one objective. Provided that x* is a non-degenerate basic solution, the problem is polynomially solvable for one objective, but remains co-NP-hard in the general case. Some open problems are mentioned at the end of the paper.

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.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bitran G.R.: Linear multiple objective problems with interval coefficients. Manage. Sci. 26, 694–706 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  2. Chinchuluun A., Pardalos P.M.: A survey of recent developments in multiobjective optimization. Ann. Oper. Res. 154, 29–50 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  3. Ehrgott M.: Multicriteria Optimization, 2nd edn. Springer, Berlin (2005)

    MATH  Google Scholar 

  4. Fiedler M., Nedoma J., Ramík J., Rohn J., Zimmermann K.: Linear Optimization Problems with Inexact Data. Springer, New York (2006)

    MATH  Google Scholar 

  5. Floudas, C.A., Pardalos, P.M. (eds): Encyclopedia of Optimization, 2nd edn. Springer, New York (2009)

    MATH  Google Scholar 

  6. Hladík M.: Computing the tolerances in multiobjective linear programming. Optim. Methods Softw. 23(5), 731–739 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  7. Hladík, M.: Interval Linear Programming: A survey. Technical report KAM-DIMATIA Series (2010-981), Department of Applied Mathematics, Charles University, Prague (2010)

  8. Hladík, M.: On necessary efficient solutions in interval multiobjective linear programming. In: Antunes, C.H., Insua, D.R., Dias, L.C. (eds.) CD-ROM Proceedings of the 25th Mini-EURO Conference Uncertainty and Robustness in Planning and Decision Making URPDM 2010, April 15–17, Coimbra, Portugal, pp. 1–10 (2010)

  9. Ida, M.: Necessary efficient test in interval multiobjective linear programming. In: Proceedings of the Eighth International Fuzzy Systems Association World Congress, pp 500–504. Taipei (August 1999)

  10. Ida M.: Portfolio selection problem with interval coefficients. Appl. Math. Lett. 16(5), 709–713 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  11. Ida M.: Solutions for the portfolio selection problem with interval and fuzzy coefficients. Reliab. Comput. 10(5), 389–400 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  12. Inuiguchi M., Sakawa M.: Possible and necessary optimality tests in possibilistic linear programming problems. Fuzzy Sets Syst. 67(1), 29–46 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  13. Inuiguchi M., Sakawa M.: Possible and necessary efficiency in possibilistic multiobjective linear programming problems and possible efficiency test. Fuzzy Sets Syst. 78(2), 231–241 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  14. Koníčková, J.: Strong unboundedness of interval linear programming problems. In: Proceedings of the 12th GAMM–IMACS Symposium on Scientific Computing, Computer Artithmetic and Validated Numerics, SCAN 2006, p. 26. (2006)

  15. Nožička F., Grygarová L., Lommatzsch K.: Geometrie konvexer Mengen und konvexe Analysis. Akademie-Verlag, Berlin (1988)

    Google Scholar 

  16. Oliveira C., Antunes C.H.: Multiple objective linear programming models with interval coefficients—an illustrated overview. Eur. J. Oper. Res. 181(3), 1434–1463 (2007)

    Article  MATH  Google Scholar 

  17. Oliveira C., Antunes C.H.: An interactive method of tackling uncertainty in interval multiple objective linear programming. J. Math. Sci. 161(6), 854–866 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  18. Padberg M.: Linear optimization and extensions, 2nd edn. Springer, Berlin (1999)

    MATH  Google Scholar 

  19. Pardalos, P.M. (ed.) Approximation and complexity in numerical optimization. Continuous and discrete problems. In: Nonconvex Optimization and Its Applications, vol. 42. Kluwer, Dordrecht (2000)

  20. Rockafellar R.T., Wets R.J.-B.: Variational Analysis. Corr. 2nd print. Springer, Berlin (2004)

    Google Scholar 

  21. Rohn J.: Linear programming with inexact data is NP-hard. Z. Angew. Math. Mech. (ZAMM) 78(Supplement 3), S1051–S1052 (1998)

    MathSciNet  MATH  Google Scholar 

  22. Rohn J.: Computing the norm ||A||∞,1 is NP-hard. Linear Multilinear Algebra 47(3), 195–204 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  23. Schrijver A.: Theory of Linear and Integer Programming. Repr. Wiley, Chichester (1998)

    MATH  Google Scholar 

  24. Wang, H.-F., Wang M.-L.: Decision analysis of the interval-valued multiobjective linear programming problems. In: Köksalan, M., Zionts, S. (eds.) Multiple criteria decision making in the new millennium. Lect. Notes Econ. Math. Syst., vol. 507, pp. 210–218. Springer, Berlin (2001)

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, 118 00, Prague, Czech Republic

    Milan Hladík

Authors
  1. Milan Hladík
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Milan Hladík.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hladík, M. Complexity of necessary efficiency in interval linear programming and multiobjective linear programming. Optim Lett 6, 893–899 (2012). https://doi.org/10.1007/s11590-011-0315-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-011-0315-1

Keywords

Search

Navigation