Skip to main content
SpringerLink
Log in

Interval linear programming under transformations: optimal solutions and optimal value range

  • Original Paper
  • Published:
Central European Journal of Operations Research Aims and scope Submit manuscript

Abstract

Interval linear programming provides a tool for solving real-world optimization problems under interval-valued uncertainty. Instead of approximating or estimating crisp input data, the coefficients of an interval program may perturb independently within the given lower and upper bounds. However, contrarily to classical linear programming, an interval program cannot always be converted into a desired form without affecting its properties, due to the so-called dependency problem. In this paper, we discuss the common transformations used in linear programming, such as imposing non-negativity on free variables or splitting equations into inequalities, and their effects on interval programs. Specifically, we examine changes in the set of all optimal solutions, optimal values and the optimal value range. Since some of the considered properties do not holds in the general case, we also study a special class of interval programs, in which uncertainty only affects the objective function and the right-hand-side vector. For this class, we obtain stronger results.

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

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Allahdadi M, Nehi HM (2012) The optimal solution set of the interval linear programming problems. Optim Lett 7(8):1893–1911. https://doi.org/10.1007/s11590-012-0530-4

    Article  Google Scholar 

  • Cerulli R, D’Ambrosio C, Gentili M (2017) Best and worst values of the optimal cost of the interval transportation problem. In: Sforza A, Sterle C (eds) Optimization and decision science: methodologies and applications: ODS, Sorrento, Italy, September 4–7, 2017, Springer International Publishing, Cham, pp 367–374. https://doi.org/10.1007/978-3-319-67308-0_37

  • Chanas S, Dubois D, Zielinski P (2002) On the sure criticality of tasks in activity networks with imprecise durations. IEEE Trans Syst Man Cybern B Cybern 32(4):393–407. https://doi.org/10.1109/TSMCB.2002.1018760

    Article  Google Scholar 

  • Cheng G, Huang G, Dong C (2015) Convex contractive interval linear programming for resources and environmental systems management. Stoch Environ Res Risk Assess 1–20. https://doi.org/10.1007/s00477-015-1187-1

  • Fortin J, Zieliński P, Dubois D, Fargier H (2010) Criticality analysis of activity networks under interval uncertainty. J Scheduling 13(6):609–627. https://doi.org/10.1007/s10951-010-0163-3

    Article  Google Scholar 

  • Grošelj P, Stirn LZ (2017) Consensus model for group decision problems with interval weights. In: Zadnik Stirn L et al (ed) Proceedings of the 14th international symposium on operational research SOR’17, Bled, Slovenia, September 27–29, 2017, Slovenian Society Informatika, Ljubljana, Slovenia, pp 535–540

  • Hladík M (2008) Tolerances in portfolio selection via interval linear programming. In: Rehorova P, Marsikova K, Hubinka Z (eds) Proceedings 26th int. conf. mathematical methods in economics MME08, Liberec, Czech Republic, Technical University Liberec, pp 185–191

  • Hladík M (2009) Optimal value range in interval linear programming. Fuzzy Optim Decis Mak 8(3):283–294. https://doi.org/10.1007/s10700-009-9060-7

    Article  Google Scholar 

  • Hladík M (2012) Interval linear programming: a survey. In: Mann ZA (ed) Linear programming—new frontiers in theory and applications. Nova Science Publishers, New York, pp 85–120 chap 2

    Google Scholar 

  • Hladík M (2017) Transformations of interval linear systems of equations and inequalities. Linear Multilinear Algebra 65(2):211–223. https://doi.org/10.1080/03081087.2016.1180339

    Article  Google Scholar 

  • Kumar P, Panda G, Gupta U (2016) An interval linear programming approach for portfolio selection model. Int J Oper Res 27(1–2):149–164. https://doi.org/10.1504/IJOR.2016.078463

    Article  Google Scholar 

  • Lai KK, Wang SY, Xu JP, Zhu SS, Fang Y (2002) A class of linear interval programming problems and its application to portfolio selection. IEEE Trans Fuzzy Syst 10(6):698–704. https://doi.org/10.1109/TFUZZ.2002.805902

    Article  Google Scholar 

  • Li W (2015) A note on dependency between interval linear systems. Optim Lett 9(4):795–797. https://doi.org/10.1007/s11590-014-0791-1

    Article  Google Scholar 

  • Mráz F (1998) Calculating the exact bounds of optimal values in LP with interval coefficients. Ann Oper Res 81:51–62. https://doi.org/10.1023/A:1018985914065

    Article  Google Scholar 

  • Novotná J, Hladík M, Masařík T (2017) Duality gap in interval linear programming. In: Zadnik Stirn L et al (ed) Proceedings of the 14th international symposium on operational research SOR’17, Bled, Slovenia, September 27–29, 2017, Slovenian Society Informatika, Ljubljana, Slovenia, pp 501–506

  • Oettli W, Prager W (1964) Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Numer Math 6(1):405–409. https://doi.org/10.1007/bf01386090

    Article  Google Scholar 

  • Oliveira C, Antunes CH (2009) A multiobjective model for integrated sustainable planning under uncertainty. In: Grasserbauer M, Sakalauskas L, Zavadskas EK (eds) Proceedings of the EURO mini-conference—5th international Vilnius conference knowledge-based technologies and OR methodologies for strategic decisions of sustainable development (KORSD-2009), pp 137–142

  • Rohn J (2006a) Interval linear programming. In: Linear optimization problems with inexact data. Springer US, pp 79–100. https://doi.org/10.1007/0-387-32698-7_3

  • Rohn J (2006b) Solvability of systems of interval linear equations and inequalities. In: Linear optimization problems with inexact data, Springer US, pp 35–77. https://doi.org/10.1007/0-387-32698-7_2

  • Safi M, Razmjoo A (2013) Solving fixed charge transportation problem with interval parameters. Appl Math Model 37(18–19):8341–8347. https://doi.org/10.1016/j.apm.2013.03.053

    Article  Google Scholar 

  • Wendell RE, Chen W (2010) Tolerance sensitivity analysis: thirty years later. Croatian Oper Res Rev 1(1):12–21

    Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Elif Garajová & Milan Hladík

  2. Department of Financial Accounting and Auditing, University of Economics, Prague, nám. W. Churchilla 4, 13067, Prague, Czech Republic

    Miroslav Rada

Authors
  1. Elif Garajová
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Milan Hladík
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Miroslav Rada
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Elif Garajová.

Additional information

The first two authors were supported by the Czech Science Foundation under Grant P403-18-04735S and by the Charles University, Project GA UK No. 156317. The third author was supported by the Czech Science Foundation under Grant P403-17-13086S.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Garajová, E., Hladík, M. & Rada, M. Interval linear programming under transformations: optimal solutions and optimal value range. Cent Eur J Oper Res 27, 601–614 (2019). https://doi.org/10.1007/s10100-018-0580-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10100-018-0580-5

Keywords

Search

Navigation