A Penalty Function Approach for Solving the Linear Trilevel Programming Problem

doi:10.1007/s40305-023-00464-6

Journal of the Operations Research Society of China ›› 2025, Vol. 13 ›› Issue (2): 616-629.doi: 10.1007/s40305-023-00464-6

Previous Articles Next Articles

A Penalty Function Approach for Solving the Linear Trilevel Programming Problem

Yan Peng, Yi-Bing Lv

School of Information and Mathematics, Yangtze University, Jingzhou 434023, Hubei, China

Received:2021-12-15 Revised:2022-09-19 Online:2025-06-30 Published:2025-07-07
Contact: Yi-Bing Lv E-mail:yibinglv@yangtzeu.edu.cn
Supported by:
This work is supported by the National Natural Science Foundation of China (Nos. 12271061,11771058) and the Outstanding Youth Foundation of Hubei Province of China (No. 2019CFA088).

Abstract

Abstract: In this paper, we mainly focus on the solving approach for the linear trilevel programming (LTP) problem. Firstly, based on the lower-level problem’s Karush-Kuhn-Tucker (K-K-T) optimality conditions, we transform the LTP problem into a bilevel programming (BP) problem with complementary constraints. Secondly, taking the complementary constraints as penalties and appending them to the upper-level objective, a penalized BP problem is obtained. Thirdly, for the penalized BP problem, we use K-K-T optimality conditions again and append the corresponding complementary conditions to the upper level as penalties. Then, an overall penalized problem for the LTP problem is formed; we analyze the characteristics of the optimal solutions of the overall penalized problem and propose a penalty function algorithm. The numerical results show that the penalty function approach is feasible and effective.

Key words: Linear trilevel programming, Karush–Kuhn–Tucker optimality conditions, Penalty function, Optimal solution

CLC Number:

90C26
90C30

Yan Peng, Yi-Bing Lv. A Penalty Function Approach for Solving the Linear Trilevel Programming Problem[J]. Journal of the Operations Research Society of China, 2025, 13(2): 616-629.

TrendMD

References

[1] Anandalingam, G., Friesz, T.L.: Hierarchical optimization: an introduction. Ann. Oper. Res. 34(1), 1-11 (1992)
[2] Bard, J.F.: Practical Bilevel Optimization. Kluwer, Boston (1998)
[3] Sana, S.S.: A production-inventory model of imperfect quality products in a three-layer supply chain. Decis. Support Syst. 50(2), 539-547 (2011)
[4] Xu, X., Meng, Z., Shen, R.: A tri-level programming model based on conditional value-at-risk for three-stage supply chain managemen. Comput. Indus. Eng. 66(2), 470-475 (2013)
[5] Luka, Z., Ori, K., Rosenzweig, V.V.: Production planning problem with sequence dependent setups as a bilevel programming problem. Eur. J. Oper. Res. 187(3), 1504-1512 (2008)
[6] Calvete, H.I., Gale, C., Oliveros, M.J.: Bilevel model for production distribution planning solved by using ant colony optimization. Comput. Operat. Res. 38(1), 320-327 (2011)
[7] Chiou, S.W.: Bilevel programming for the continuous transport network design problem. Transp. Res. Part B 39(4), 361-383 (2005)
[8] Feng, C., Wen, C.: A fuzzy bi-level and multi-objective model to control traffic flow into the disaster area post earthquake. J. Eastern Asia Soc. Transp. Stud. 6, 4253-4268 (2005)
[9] Ke, G.Y., Bookbinder, J.H.: Coordinating the discount policies for retailer, wholesaler, and less-than-truckload carrier under price-sensitive demand: a tri-level optimization approach. Int. J. Prod. Econ. 196, 82-100 (2018)
[10] Safaei, A.S., Farsad, S., Paydar, M.M.: Robust bi-level optimization of relief logistics operations. Appl. Math. Model. 56, 359-380 (2017)
[11] Bard, J.F.: Optimality conditions for the bilevel programming problem. Naval Res. Logistics Quarter. 31, 13-26 (1984)
[12] Omar, B.: Bilevel linear programming. Comput. Operat. Res. 20, 485-501 (1993)
[13] Cao, D., Leung, L.C.: A partial cooperation model for non-unique linear two-level decision problems. Eur. J. Oper. Res. 140(1), 134-141 (2007)
[14] Chiou, S.W.: A bi-level programming for logistics network design with system-optimized flows. Inf. Sci. 179(14), 2434-2441 (2009)
[15] Alguacil, N., Delgadillo, A., Arroyo, J.M.: A trilevel programming approach for electric grid defense planning. Comput. Operat. Res. 41, 282-290 (2014)
[16] Li, G., Wan, Z., Chen, J.W., Zhao, X.: Optimality conditions for pessimistic trilevel optimization problem with middle-level problem being pessimistic. J. Nonlinear Sci. Appl. 9, 3864-3878 (2016)
[17] Li, G., Wan, Z., Chen, J.W., Zhao, X.: Necessary optimality condition for trilevel optimization problem. J. Indus. Manage. Optimiz. 16(1), 55-70 (2020)
[18] Faisca, N.P., Saraiva, P.M., Rustem, B., Pistikopoulos, E.N.: A multi- parametric programming approach for multilevel hierarchical and decentralised optimisation problems. CMS 6(4), 377-397 (2009)
[19] Zhao, X., Zheng, Y., Wan, Z.: Interactive intuitionistic fuzzy methods for multilevel programming problems. Expert Syst. Appl. 72, 258-268 (2016)
[20] Bard, J.F.: An investigation of the linear three level programming problem. IEEE Trans. Syst. Man Cybern. 14(5), 711-717 (1984)
[21] Zhang, G.Q., Lu, J., Montero, J., Yi, Z.: Model, solution concept, and kth-best algorithm for linear trilevel programming. Inf. Sci. 180(4), 481-492 (2010)
[22] Lv, Y., Jiang, J.: A relaxation solving approach for the linear trilevel programming problem. Comput. Appl. Math. 40, 226 (2021)
[23] Anandalingam, G., White, D.J.: A solution method for the linear static stackelberg problem using penalty functions. IEEE Trans. Autom. Control 35(10), 1170-1173 (1990)
[24] Shih, H.S., Lai, Y.J., Lee, E.S.: Fuzzy approach for multi-level programming problems. Comput. Operat. Res. 23(1), 73-91 (1996)

A Penalty Function Approach for Solving the Linear Trilevel Programming Problem

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	Sumit Kumar Maiti, Sankar Kumar Roy. Bi-level Programming for Stackelberg Game with Intuitionistic Fuzzy Number: a Ranking Approach [J]. Journal of the Operations Research Society of China, 2021, 9(1): 131-149.
[2]	Promila Kumar, Bharti Sharma, Jyoti Dagar. Interval-Valued Programming Problem with Infinite Constraints [J]. Journal of the Operations Research Society of China, 2018, 6(4): 611-626.
[3]	Jue-You Li · Zhi-You Wu · Qiang Long. A New Objective Penalty Function Approach for Solving Constrained Minimax Problems [J]. Journal of the Operations Research Society of China, 2014, 2(1): 93-108.