Kybernetika 59 no. 1, 64-87, 2023

Robust optimality analysis for linear programming problems with uncertain objective function coefficients: an outer approximation approach

Zhenzhong Gao and Masahiro InuiguchiDOI: 10.14736/kyb-2023-1-0064


Linear programming (LP) problems with uncertain objective function coefficients (OFCs) are treated in this paper. In such problems, the decision-maker would be interested in an optimal solution that has robustness against uncertainty. A solution optimal for all conceivable OFCs can be considered a robust optimal solution. Then we investigate an efficient method for checking whether a given non-degenerate basic feasible (NBF) solution is optimal for all OFC vectors in a specified range. When the specified range of the OFC vectors is a hyper-box, i. e., the marginal range of each OFC is given by an interval, it has been shown that the tolerance approach can efficiently solve the robust optimality test problem of an NBF solution. However, the hyper-box case is a particular case where the marginal ranges of some OFCs are the same no matter what values the remaining OFCs take. In real life, we come across cases where some OFCs' marginal ranges depend on the remaining OFCs' values. For example, the prices of products rise together in tandem with raw materials, the gross profit of exported products increases while that of imported products decreases because they depend on the currency exchange rates, and so on. Considering those dependencies, we consider a case where the range of the OFC vector is specified by a convex polytope. In this case, the tolerance approach to the robust optimality test problem of an NBF solution becomes in vain. To treat the problem, we propose an algorithm based on the outer approximation approach. By numerical experiments, we demonstrate how the proposed algorithm efficiently solves the robust optimality test problems of NBF solutions compared to a conventional vertex-listing method.


linear programming problems, interactive uncertain coefficients, robust optimality analysis, outer approximation approach, convex polytope


90C05, 52B12


  1. S. P. Bradley, A. C. Hax and T. L. Magnanti: Applied Mathematical Programming. Addison-Wesley Publishing Company, 1977.   CrossRef
  2. S. Curry, I. Lee, S. Ma and N. Serban: Global sensitivity analysis via a statistical tolerance approach. Europ. J. Oper. Res. 296 (2022), 1, 44-59.   DOI:10.1016/j.ejor.2021.04.004
  3. G. Dantzig: Linear programming and extensions. In: Linear programming and extensions. Princeton Zniversity Press, 2016.   CrossRef
  4. C. Filippi: A fresh view on the tolerance approach to sensitivity analysis in linear programming. Europ. J. Oper. Res. 16 (2005), 1, 1-19.   DOI:10.1016/j.ejor.2004.01.050
  5. Z. Gao and M. Inuiguchi: Estimating the optimal probability of a candidate basic solution in stochastic linear programming. In: 60th Annual Conference of the Society of Instrument and Control Engineers of Japan (SICE), IEEE 2021, pp. 640-643.   CrossRef
  6. Z. Gao and M. Inuiguchi: An analysis to treat the degeneracy of a basic feasible solution in interval linear programming. In: The Ninth International Symposium on Integrated Uncertainty in Knowledge Modelling and Decision Making (IUKM 2022). Publ. in Lecture Notes in Computer Science pp. 130-142, 2022.   DOI:10.1007/978-3-030-98018-4\_11
  7. E. Garajová and M. Hladík: On the optimal solution set in interval linear programming. Comput. Optim. Appl. 72 (2019), 1, 269-292.   DOI:10.1007/s10589-018-0029-8
  8. T. L. Heath et al.: The works of Archimedes. Courier Corporation, 2002.   CrossRef
  9. M. Henk, J. Richter-Gebert, G. M. Ziegler. \newblock Basic properties of convex polytopes. \newblock In J. Goodman, J. O'Rourke, editors, {\em Handbook of Discrete, Computational Geometry, 2nd Edition}, pages 243-270, Boca Raton, FL and 2004. CRC Press.:     CrossRef
  10. M. Hladík: Multiparametric linear programming: support set and optimal partition invariancy. Europ. J. Oper. Res. 202 (2010), 1, 25-31, 2010.   DOI:10.1016/j.ejor.2009.04.019
  11. M. Hladík: Complexity of necessary efficiency in interval linear programming and multiobjective linear programming. Optim. Lett. 6 (2012), 5, 893-899.   DOI:10.1007/s11590-011-0315-1
  12. R. Horst, J. De Vries and N. V. Thoai: On finding new vertices and redundant constraints in cutting plane algorithms for global optimization. Oper. Res. Lett. 7 (1988), 2, 85-90.   DOI:10.1016/0167-6377(88)90071-5
  13. R. Horst and H. Tuy: Global optimization: Deterministic approaches. Springer Science and Business Media, 2013.   CrossRef
  14. M. Inuiguchi: Necessary efficiency is partitioned into possible and necessary optimalities. In: 2013 Joint IFSA World Congress and NAFIPS Annual Meeting (IFSA/NAFIPS), IEEE 2013, pp. 209-214.   DOI:10.1109/IFSA-NAFIPS.2013.6608401
  15. M. Inuiguchi, Z. Gao and C. O. Henriques: Robust optimality analysis of non-degenerate basic feasible solutions in linear programming problems with fuzzy objective coefficients. Fuzzy Optimization and Decision Making 22 (2023), 51-79.   DOI:10.1007/s10700-022-09383-2
  16. M. Inuiguchi and J. Ramík: Possibilistic linear programming: a brief review of fuzzy mathematical programming and a comparison with stochastic programming in portfolio selection problem. Fuzzy Sets Systems 111 (2000), 1, 3-28.   DOI:10.1016/S0165-0114(98)00449-7
  17. M. Inuiguchi and M. Sakawa: Possible and necessary efficiency in possibilistic multiobjective linear programming problems and possible efficiency test. Fuzzy Sets Systems 78 (1996), 2, 231-241.   DOI:10.1016/0165-0114(95)00169-7
  18. M. Inuiguchi and M. Sakawa: An achievement rate approach to linear programming problems with an interval objective function. J. Oper. Res. Soc. 48 (1997), 1, 25-33.   DOI:10.1038/sj.jors.2600322
  19. M. Inuiguchi and M. Sakawa: Robust optimization under softness in a fuzzy linear programming problem. Int. J. Approx. Reas. 18 (1998), 1-2, 21-34.   DOI:10.1016/s0888-613x(97)10002-0
  20. B. Jansen, J. De Jong, C. Roos and T. Terlaky: Sensitivity analysis in linear programming: just be careful! Europ. J. Oper. Res. 101 (1997), 1, 15-28.   DOI:10.1016/s0377-2217(96)00172-5
  21. P. Kall and J. Mayer: Stochastic Linear Programming: Models, Theory, and Computation. Second Edition. Springer, Boston 2011.   CrossRef
  22. M. J. Todd: Probabilistic models for linear programming. Math. Oper. Res. 16 (1991), 4, 671-693.   DOI:10.1287/moor.16.4.671
  23. R. E. Wendell: The tolerance approach to sensitivity analysis in linear programming. Management Sci. 31 (1985), 5, 564-578.   DOI:10.1287/mnsc.31.5.564
  24. R. E. Wendell: Tolerance sensitivity and optimality bounds in linear programming. Management Sci. 50 (2004), 6, 797-803.   DOI:10.1287/mnsc.1030.0221
  25. F. R. Wondolowski Jr.: A generalization of wendell's tolerance approach to sensitivity analysis in linear programming. Decision Sci. 22 (1991), 4, 792-811.   DOI:10.1111/j.1540-5915.1991.tb00365.x