A Solution Method for Stochastic Multilevel Programming Problems. A Systematic Sampling Evolutionary Approach

• Autorzy: Natnael, Nigussie Goshu , Semu, Mitiku Kassa
• Języki publikacji: EN

Abstrakty

EN

Stochastic multilevel programming is a mathematical programming problem with some given number of hierarchical levels of decentralized decision makers and having some kind of randomness properties in the problem definition. The introduction of some randomness property in its hierarchical structure makes stochastic multilevel problems computationally challenging and expensive. In this article, a systematic sampling evolutionary method is adapted to solve the problem. The solution procedure is based on realization of the random variables and systematic partitioning of each hierarchical level's decision space for searching an optimal reaction. The search goes sequentially upwards starting from the bottom up through the top hierarchical level problem. The existence of solution and convergence of the solution procedure is shown. The solution procedure is implemented and tested on some selected deterministic test problems from literature. Moreover, the proposed algorithm can be used to solve stochastic multilevel programming problems with additional complexity in their problem definition. (original abstract)

Słowa kluczowe

EN

Mathematical programming; Stochastic programming; Stochastic models

PL

Programowanie matematyczne; Programowanie stochastyczne; Modele stochastyczne

• Czasopismo: Operations Research and Decisions
• Rocznik: 2024
• Tom: 34
• Numer: nr 1
• Strony: 149--174

Twórcy

autor

Natnael, Nigussie Goshu

• Addis Ababa Science and Technology University, Addis Ababa, Ethiopia

autor

Semu, Mitiku Kassa

• Botswana International University of Science and Technology, Palapye, Botswana

Bibliografia

• 1] Acevedo, J., and Pistikopoulos, E. N. A multiparametric programming approach for linear process engineering problems under uncertainty. Industrial Engineering Chemistry Research 36, 3 (1997), 717-728.
• [2] Ahmadi-Moshkenani, P., Johansen, T. A., and Olaru, S. Combinatorial approach towards multi-parametric quadratic programming based on characterizing adjacent critical regions. IEEE Transactions on Automatic Control 63, 10 (2018), 3221-3231.
• [3] Alemdar, N. M., and Sirakaya, S. Online computation of Stackelberg equilibria with synchronous parallel genetic algorithms. Journal of Economic Dynamics and Control 27, 8 (2003), 1503-1515.
• [4] Alizadeh, S. M., Marcotte, P., and Savard, G. Two stage stochastic bilevel programming over a transportation network. Transportation Research Part B: Methodological 58 (2013), 92-105.
• [5] Audestad, J.-A., Gaivoronski, A. A., and Werner, S. Extending the stochastic programming framework for the modeling of several decision makers: pricing and competition in the telecommunication sector. Annals of Operations Research 142 (2006), 19-39.
• [6] Avraamidou, S., and Pistikopoulos, E. N. Multi-parametric global optimization approach for trilevel mixed-integer linear optimization problems. Journal of Global Optimization 74 (2019), 443-465.
• [7] Avraamidou, S., and Pistikopoulos, E. N. A multi-parametric optimization approach for bilevel mixed-integer linear and quadratic programming problems. Computers & Chemical Engineering 125 (2019), 98-113.
• [8] Awraris, A., Wordofa, B. G., and Kassa, S. M. A simplex-based branch-and-cut method for solving integer trilevel programming problems. Journal of Mathematics and Computer Science 25 (2022), 232-250.
• [9] Axehill, D., Besselmann, T., Raimondo, D. M., and Morari, M. A parametric branch and bound approach to suboptimal explicit hybrid MPC. Automatica 50, 1 (2014), 240-246.
• [10] Bard, J. A grid search algorithm for the linear bilevel programming problem. In Proceedings of the 14th Annual Meeting of the American Institute for Decision Science (1982), pp. 256-258.
• [11] Ben-Ayed, O. Bilevel linear programming. Computer and Operations Research 20, 5 (1993), 485-501.
• [12] Beykal, B., Avraamidou, S., and Pistikopoulos, E. N. Bi-level mixed-integer data-driven optimization of integrated planning and scheduling problems. In 31st European Symposium on Computer Aided Process Engineering, M. Türkay and R. Gani, Eds., vol. 50 of Computer Aided Chemical Engineering. Elsevier, 2021, pp. 1707-1713.
• [13] Beykal, B., Avraamidou, S., and Pistikopoulos, E. N. Data-driven optimization of mixed-integer bi-level multi-follower integrated planning and scheduling problems under demand uncertainty. Computers & Chemical Engineering 156 (2022), 107551.
• [14] Beykal, B., Avraamidou, S., Pistikopoulos, I. P. E., Onel, M., and Pistikopoulos, E. N. DOMINO: Data-driven Optimization of bi-level Mixed-Integer NOnlinear Problems. Journal of Global Optimization 78 (2020), 1-36.
• [15] Bialas, W. F., and Karwan, M. K. Mathematical Methods for Multilevel Planning. Research Report No. 79-2, Department of Industrial Engineering, State university of New York at Buffalo, NY, 1979.
• [16] Borrelli, F., Bemporad, A., and Morari, M. Geometric algorithm for multiparametric linear programming. Journal of Optimization Theory and Applications 118, 3 (2003), 515-540.
• [17] Bracken, J., and McGill, J. T. Mathematical programs with optimization problems in the constraints. Operations Research 21, 1 (1973), 37-44.
• [18] Bracken, J., and McGill, J. T. Technical note - A method for solving mathematical problems with nonlinear programs in the constraints. Operations Research 22, 5 (1974), 1097-110l.
• [19] Christiansen, S., Patriksson, M., and Wynter, L. Stochastic bilevel programming in structural optimization. Structural and Multidisciplinary Optimization 21, 5 (2001), 361-371.
• [20] Dempe, S. Foundations of Bilevel Programming. Kluver Academic Publisers, New York, NY, 2002.
• [21] Dempe, S. Comment to "interactive fuzzy goal programming approach for bilevel programming problem" by S. R. Arora and R. Gupta. European Journal of Operational Research 212, 2 (2011), 429-431.
• [22] Dempe, S. Bilevel Optimization: Theory, Algorithms and Applications. Preprint 2018-11, Fakultät für Mathematik und Informatik, TU Bergakademie Freiberg, 2018.
• [23] Dempe, S., Ivanov, S., and Naumov, A. Reduction of the bilevel stochastic optimization problem with quantile objective function to a mixed-integer problem. Applied Stochastic Models in Business Industry 33, 5 (2017), 544-554.
• [24] Faísca, N. P., Saraiva, P. M., Rustem, B., and Pistikopoulos, E. N. A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems. Computational Management Science 6, 4 (2009), 377-397.
• [25] Goshu, N. N., and Kassa, S. M. A systematic sampling evolutionary (SSE) method for stochastic bilevel programming problems. Computers and Operations Research 120 (2020), 104942.
• [26] Goshu, N. N., and Kassa, S. M. Stochastic bilevel programming with multiple followers: A solution approach using the systematic sampling evolutionary method. Engineering Optimization 54, 6 (2022), 1059-1072.
• [27] Goshu, N. N., and Kassa, S. M. Stochastic sequential supply chain management system: with a solution approach using the systematic sampling evolutionary method. International Journal of Business Performance and Supply Chain Modelling 13, 3 (2022), 264-288.
• [28] Han, J., Zhang, G., Hu, Y., and Lu, J. Solving trilevel programming problems using a particle swarm optimization algorithm. In Proceedings of the 10th IEEE Conference on Industrial Electronics and Applications, (Auckland, New Zealand), 2015, IEEE, pp. 569-574.
• [29] Han, J., Zhang, G., Hu, Y., and Lu, J. A solution to bi/trilevel programming problems using particle swarm optimization. Information Sciences 370-371 (2016), 519-537.
• [30] Hosseini, E. Presentation and solving non-linear quad-level programming problem utilizing a heuristic approach based on Taylor theorem. Journal of Optimization in Industrial Engineering 11, 1 (2018), 91-101.
• [31] Ivanov, S. A bilevel stochastic programming problem with random parameters in the follower's objective function. Journal of Applied and Industrial Mathematics 12, 4 (2018), 658-667 .
• [32] Kassa, A. M., and Kassa, S. M. A multi-parametric programming algorithm for special classes of non-convex multilevel optimization problems. An International Journal of Optimization and Control: Theories & Applications 3, 2 (2013), 133-144.
• [33] Kassa, A. M., and Kassa, S. M. Approximate solution algorithm for multi-parametric non-convex programming problems with polyhedral constraints. An International Journal of Optimization and Control: Theories & Applications 4, 2 (2014), 89-98.
• [34] Kassa, A. M., and Kassa, S. M. A branch-and-bound multi-parametric programming approach for non-convex multilevel optimization with polyhedral constraints. Journal of Global Optimization 64, 4 (2016), 745-764.
• [35] Kassa, A. M., and Kassa, S. M. Deterministic solution approach for some classes of nonlinear multilevel programs with multiple followers. Journal of Global Optimization 68, 4 (2017), 729-747.
• [36] Kassa, S. M. Three-level global resource allocation model for HIV controle: A hierarchical decision system approach. Mathematical Biosciences and Engineering 15, 1 (2018), 255-273.
• [37] Kassa, S. M., and Tsegay, T. H. An iterative method for trilevel quadratic fractional programming problems using fuzzy goal programming approach. Journal of Industrial Engineering International 14, 2 (2018), 255-264.
• [38] Kim, S., Pasupathy, R., and Henderson, S. G. A Guide to Sample Average Approximation. In Handbook of Simulation Optimization, C. M. Fu, Ed., vol. 216 of International Series in Operations Research & Management Science, Springer, New York, NY, 2015, pp. 207-243.
• [39] Kumar, M., and Pal, B. B. Fuzzy goal programming approach to chance constrained multilevel programming problems. International Journal of Advanced Computer Research 3, 8 (2013), 193-200.
• [40] Lv, Y., and Jiang, J. A relaxation solving approach for the linear trilevel programming problem. Computational and Applied Mathematics 40, 6 (2021), 226.
• [41] Molla, A. A Multiparametric Programming Approach for Multilevel Optimization. MSc thesis, Department of Mathematics, Addis Ababa University, 2011.
• [42] Pappas, I., Diangelakis, N. A., and Pistikopoulos, E. N. The exact solution of multiparametric quadratically constrained quadratic programming problems. Journal of Global Optimization 79, 1 (2021), 59-85.
• [43] Patriksson, M. On the applicability and solution of bilevel optimization models in transportation science: A study on the exis- tence, stability and computation of optimal solutions to stochastic mathematical programs with equilibrium constraints. Transportation Research Part B: Methodological 42, 10 (2008), 843-860.
• [44] Patriksson, M., and Wynter, L. Stochastic mathematical programs with equilibrium constraints. Operation Research Letters 25, 4 (1999), 159-167.
• [45] Pistikopoulos, E. N., Georgidis, M. C., and Dua, V. Multi-Parametric Programming: Theory, Algorithms and Applications. Vol. 1, Wiley-VCH, Weinheim, 2007.
• [46] Pramanik, S., and Banerjee, D. Chance constrained quadratic bi-level programming problem. International Journal of Modern Engineering Research 2, 4 (2012), 2417-2424.
• [47] Pramanik, S., Banerjee, D., and Giri, B. Chance constrained linear plus linear fractional bilevel programming problem. International Journal of Computer Applications 56, 16 (2012), 34-39.
• [48] Pramanik, S., Banerjee, D., and Giri, B. Chance constrained multi-level linear programming problem. International Journal of Computer Applications 120, 18 (2015), 1-6.
• [49] Robbins, H., and Monro, S. A stochastic approximation method. The Annals of Mathematics Statistics 22, 3 (1951), 400-407.
• [50] Sakawa, M., Nishizaki, I., and Uemura, Y. Interactive fuzzy programming for multilevel linear programming problems. Computers and Mathematics with Applications 36, 2 (1998), 71-86.
• [51] Shi, C., Zhang, G., and Lu, J. The Kth-best approach for linear bilevel multi-follower programming. Journal of Global Optimization 33, 4 (2005), 563-578.
• [52] Smola, A. J., Vishwanathan, S. V. N., and Le, Q. V. Bundle methods for machine learning. In Advances in Neural Information Processing Systems 20 (NIPS 2007), J. Platt, D. Koller, Y. Singer and S. Roweis, Eds., Curran Associates, Inc., 2008, pp. 1377-1384.
• [53] von Stackelberg, H. The Theory of the Market Economy. Oxford University Press, New York, NY, 1952.
• [54] Tilahun, S. L., Kassa, S. M., and Ong, H. C. A new algorithm for multilevel optimization problems using evolutionary strategy, inspired by natural adaptation. In PRICAI 2012: Trends in Artificial Intelligence , P. Anthony, M. Ishizuka, and D. Lukose, Eds., vol. 7458, (Berlin, Heidelberg, 2012), Springer, pp. 577-588.
• [55] Vallée, T., and Başar, T. Off-line computation of Stackelberg solutions with the genetic algorithm. Computational Economics 13, 3 (1999), 201-209.
• [56] Vicente, L. N., and Calamai, P. H. Bilevel and multilevel programming: A bibliography review. Journal of Global Opti- mization 5, 3 (1994), 291-306.
• [57] Wang, Y., Jiao, Y.-C., and Li, H. An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme. IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews 35, 2 (2005), 221-232.
• [58] Werner, S. Bilevel Stochastic Programming Problems: Analysis and Application to Telecommunications. PhD thesis, Norwegian University of Science and Technology, Trondheim 2004.
• [59] White, D. J. Multilevel programming, rational reaction sets, and efficient solutions. Journal of Optimization Theory and Applications 87, 3 (1995), 727-746.
• [60] Woldemariam, A. T., and Kassa, S. M. Systematic evolutionary algorithm for general multilevel Stackelberg problems with bounded decision variables (SEAMSP). Annals of Operations Research 229, 1 (2015), 771-790.
• [61] Yeh, K., Whittaker, C., Realff, M. J., and Lee, J. H. Two stage stochastic bilevel programming model of a preestablished timberlands supply chain with biorefinery investment interests. Computers and Chemical Engineering, Elsevier 73, 2 (2015), 141-153.
• [62] Zewde, A. B., and Kassa, S. M. A novel approach for solving multi-parametric problems with nonlinear constraints. Journal of Global Optimization 85, 2 (2023), 283-313.
• [63] Zhan, Y., and Zheng, Q. P. A multistage decision-dependent stochastic bilevel programming approach for power generation investment expansion planning. IISE Transactions 50, 8 (2018), 720-734.
• [64] Zhang, G., Lu, J., Montero, J., and Zeng, Y. Model, solution concept, and Kth-best algorithm for linear trilevel programming. Information Sciences 180, 4 (2010), 481-492.

Identyfikatory

DOI

10.37190/ord240108