First step immersion in interval linear programming with linear dependencies

Document Type: ORO2013


1 Department of Applied Mathematics‎, ‎Faculty of Mathematics and Physics‎, ‎Charles University in Prague‎, ‎Malostranske Nam‎. ‎25‎, ‎11800‎, ‎Prague‎, ‎Czech Republic.

2 Department of Econometrics‎, ‎University of Economics‎, ‎n'am. W. Churchilla 4‎, ‎13067‎, ‎Prague‎, ‎Czech Republic.


‎We consider a linear programming problem in a general form and suppose that all coefficients may vary in some prescribed intervals‎. ‎Contrary to classical models‎, ‎where parameters can attain any value from the interval domains independently‎, ‎we study problems with linear dependencies between the parameters‎. ‎We present a class of problems that are easily solved by reduction to the classical case‎. ‎In contrast‎, ‎we also show a class of problems with very simple dependencies‎, ‎which appear to be hard to deal with‎. ‎We also point out some interesting open problems‎.


Main Subjects

G. Alefeld and J. Herzberger, Introduction to Interval Computations, Computer Science and Applied Mathematics, Academic Press, New York, 1983.

M. Allahdadi and H. Mishmast Nehi, The optimal solution set of the interval linear programming problems, Optim. Lett. 7 (2013), no. 8, 1893--1911.

J. W. Chinneck and K. Ramadan, Linear programming with interval coeficients, J. Oper. Res. Soc. 51 (2000), no. 2, 209--220.

M. Fiedler, J. Nedoma, J. Ramik, J. Rohn and K. Zimmermann, Linear Optimization Problems with Inexact Data, Springer, New York, 2006.

V. Gabrel, C. Murat and N. Remli, Linear programming with interval right hand sides. Int. Trans. Oper. Res. 17 (2010), no. 3, 397--408.

M. Hladik, Solution set characterization of linear interval systems with a specific dependence structure, Reliab. Comput. 13 (2007), no. 4, 361--374.

M. Hladik, Optimal value range in interval linear programming, Fuzzy Optim. Decis. Mak. 8 (2009), no. 3, 283--294.

M. Hladik, Complexity of necessary eficiency in interval linear programming and multiobjective linear programming, Optim. Lett. 6 (2012), no. 5, 893--899.

M. Hladik, Interval linear programming: a survey, in: Z. A. Mann (ed.), Linear Programming - New Frontiers in Theory and Applications, Chapter 2, pp. 85--120, Nova Science Publishers, New York, 2012.

M. Hladik, An interval linear programming contractor, in: J. Ramik and D. Stavarek (eds.), Proceedings 30th Int. Conf. Mathematical Methods in Economics 2012, Karvina, Czech Republic, pp. 284--289, Silesian University in Opava, 2012.

M. Hladik, Weak and strong solvability of interval linear systems of equations and inequalities, Linear Algebra Appl. 438 (2013), no. 11, 4156--4165.

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

M. Hladik, On approximation of the best case optimal value in interval linear programming, Optim. Lett. 8 (2014), no. 7, 1985--1997.

M. Hladik, Strong solvability of linear interval systems of inequalities with simple dependencies, Int. J. Fuzzy Comput. Model. 1 (2014), no. 1, 3--14.

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

 W. Li, J. Luo and C. Deng, Necessary and su_cient conditions of some strong optimal solutions to the interval linear programming, Linear Algebra Appl. 439 (2013), no. 10, 3241--3255.

J. Luo and W. Li, Strong optimal solutions of interval linear programming, Linear Algebra Appl. 439 (2013), no. 8, 2479--2493.

J. Luo, W. Li and Q. Wang, Checking strong optimality of interval linear programming with inequality constraints and nonnegative constraints, J. Comput. Appl. Math. 260 (2014) 180--190.

R. E. Moore, R. B. Kearfott and M. J. Cloud, Introduction to Interval Analysis, SIAM, Philadelphia, 2009.

F. Mraz, Calculating the exact bounds of optimal values in LP with interval coeficients, Ann. Oper. Res. 81 (1998) 51--62.

A. Neumaier, Interval Methods for Systems of Equations, Cambridge Univ. Press, Cambridge, 1990.

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

M. Soleimani-damaneh and G. R. Jahanshahloo, Optimal and strongly optimal solutions for linear programming models with variable parameters, Appl. Math. Lett. 20 (2007), no. 10, 1052--1056.

S. Vajda, Mathematical Programming, Addison-Wesley Series in Statistics, Addison-Wesley Publishing, Reading, Mass.London 1961.