Geodesic
Robust optimality analysis for linear programming problems with uncertain objective function coefficients: an outer approximation approach
Kybernetika, Tome 59 (2023) no. 1, pp. 64-87
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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 (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.
DOI : 10.14736/kyb-2023-1-0064
Classification : 52B12, 90C05
Keywords: linear programming problems; interactive uncertain coefficients; robust optimality analysis; outer approximation approach; convex polytope 
@article{10_14736_kyb_2023_1_0064,
     author = {Gao, Zhenzhong and Inuiguchi, Masahiro},
     title = {Robust optimality analysis for linear programming problems with uncertain objective function coefficients: an outer approximation approach},
     journal = {Kybernetika},
     pages = {64--87},
     year = {2023},
     volume = {59},
     number = {1},
     doi = {10.14736/kyb-2023-1-0064},
     mrnumber = {4567842},
     zbl = {07675643},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-1-0064/}
}
TY  - JOUR
AU  - Gao, Zhenzhong
AU  - Inuiguchi, Masahiro
TI  - Robust optimality analysis for linear programming problems with uncertain objective function coefficients: an outer approximation approach
JO  - Kybernetika
PY  - 2023
SP  - 64
EP  - 87
VL  - 59
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-1-0064/
DO  - 10.14736/kyb-2023-1-0064
LA  - en
ID  - 10_14736_kyb_2023_1_0064
ER  - 
%0 Journal Article
%A Gao, Zhenzhong
%A Inuiguchi, Masahiro
%T Robust optimality analysis for linear programming problems with uncertain objective function coefficients: an outer approximation approach
%J Kybernetika
%D 2023
%P 64-87
%V 59
%N 1
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-1-0064/
%R 10.14736/kyb-2023-1-0064
%G en
%F 10_14736_kyb_2023_1_0064
Gao, Zhenzhong; Inuiguchi, Masahiro. Robust optimality analysis for linear programming problems with uncertain objective function coefficients: an outer approximation approach. Kybernetika, Tome 59 (2023) no. 1, pp. 64-87. doi: 10.14736/kyb-2023-1-0064

[1] Bradley, S. P., Hax, A. C., Magnanti, T. L.: Applied Mathematical Programming. Addison-Wesley Publishing Company, 1977. | MR

[2] Curry, S., Lee, I., Ma, S., Serban, N.: Global sensitivity analysis via a statistical tolerance approach. Europ. J. Oper. Res. 296 (2022), 1, 44-59. | DOI | MR

[3] Dantzig, G.: Linear programming and extensions. In: Linear programming and extensions. Princeton Zniversity Press, 2016. | MR

[4] Filippi, C.: A fresh view on the tolerance approach to sensitivity analysis in linear programming. Europ. J. Oper. Res. 16 (2005), 1, 1-19. | DOI | MR

[5] Gao, Z., Inuiguchi, M.: 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.

[6] Gao, Z., Inuiguchi, M.: 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

[7] Garajová, E., Hladík, M.: On the optimal solution set in interval linear programming. Comput. Optim. Appl. 72 (2019), 1, 269-292. | DOI | MR

[8] al., T. L. Heath et: The works of Archimedes. Courier Corporation, 2002. | MR

[9] Henk, M., Richter-Gebert, J., Goodman, G. M. Ziegler.: Basic properties of convex polytopes. In J. O'Rourke, J. editors Discrete, Handbook of Geometry, Computational Edition, 2nd 243-270, pages Raton, Boca FL Press., 2004. CRC | MR

[10] Hladík, M.: Multiparametric linear programming: support set and optimal partition invariancy. Europ. J. Oper. Res. 202 (2010), 1, 25-31, 2010. | DOI | MR

[11] Hladík, M.: Complexity of necessary efficiency in interval linear programming and multiobjective linear programming. Optim. Lett. 6 (2012), 5, 893-899. | DOI | MR

[12] Horst, R., Vries, J. De, Thoai, N. V.: On finding new vertices and redundant constraints in cutting plane algorithms for global optimization. Oper. Res. Lett. 7 (1988), 2, 85-90. | DOI | MR

[13] Horst, R., Tuy, H.: Global optimization: Deterministic approaches. Springer Science and Business Media, 2013. | MR

[14] Inuiguchi, M.: 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

[15] Inuiguchi, M., Gao, Z., Henriques, C. O.: 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 | MR

[16] Inuiguchi, M., Ramík, J.: 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 | MR

[17] Inuiguchi, M., Sakawa, M.: Possible and necessary efficiency in possibilistic multiobjective linear programming problems and possible efficiency test. Fuzzy Sets Systems 78 (1996), 2, 231-241. | DOI | MR

[18] Inuiguchi, M., Sakawa, M.: An achievement rate approach to linear programming problems with an interval objective function. J. Oper. Res. Soc. 48 (1997), 1, 25-33. | DOI

[19] Inuiguchi, M., Sakawa, M.: Robust optimization under softness in a fuzzy linear programming problem. Int. J. Approx. Reas. 18 (1998), 1-2, 21-34. | DOI | MR

[20] Jansen, B., Jong, J. De, Roos, C., Terlaky, T.: Sensitivity analysis in linear programming: just be careful!. Europ. J. Oper. Res. 101 (1997), 1, 15-28. | DOI

[21] Kall, P., Mayer, J.: Stochastic Linear Programming: Models, Theory, and Computation. Second Edition. Springer, Boston 2011. | MR

[22] Todd, M. J.: Probabilistic models for linear programming. Math. Oper. Res. 16 (1991), 4, 671-693. | DOI | MR

[23] Wendell, R. E.: The tolerance approach to sensitivity analysis in linear programming. Management Sci. 31 (1985), 5, 564-578. | DOI | MR

[24] Wendell, R. E.: Tolerance sensitivity and optimality bounds in linear programming. Management Sci. 50 (2004), 6, 797-803. | DOI

[25] Jr., F. R. Wondolowski: A generalization of wendell's tolerance approach to sensitivity analysis in linear programming. Decision Sci. 22 (1991), 4, 792-811. | DOI

Cité par Sources :