×

A reducibility method for the weak linear bilevel programming problems and a case study in principal-agent. (English) Zbl 1440.90057

Summary: A weak linear bilevel programming (WLBP) problem often models problems involving hierarchy structure in expert and intelligent systems under the pessimistic point. In the paper, we deal with such a problem. Using the duality theory of linear programming, the WLBP problem is first equivalently transformed into a jointly constrained bilinear programming problem. Then, we show that the resolution of the jointly constrained bilinear programming problem is equivalent to the resolution of a disjoint bilinear programming problem under appropriate assumptions. This may give a possibility to solve the WLBP problem via a single-level disjoint bilinear programming problem. Furthermore, some examples illustrate the solution process and feasibility of the proposed method. Finally, the WLBP problem models a principal-agent problem under the pessimistic point that is also compared with a principal-agent problem under the optimistic point.

MSC:

90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Aboussoror, A.; Mansouri, A., Weak linear bilevel programming problems: existence of solutions via a penalty method, J. Math. Anal. Appl., 304, 399-408 (2005) · Zbl 1074.90025
[2] Aboussoror, A.; Mansouri, A., Existence of solutions to weak nonlinear bilevel problems via minsup and d.c. problems, RAIRO Oper. Res., 42, 87-103 (2008) · Zbl 1151.49010
[3] Aboussoror, A.; Adly, S.; Jalby, V., Weak nonlinear bilevel problems: existence of solutions via reverse convex and convex maximization problems, J. Indus. Manage. Optim., 7, 559-571 (2011) · Zbl 1257.90074
[4] Alarie, S.; Audet, C.; Jaumard, B.; Savard, G., Concavity cuts for disjoint bilinear programming, Math. Program., 90, 2, 373-398 (2001) · Zbl 0989.90106
[5] Al-Khayyal, F. A., Jointly constrained bilinear programs and related problems: an overview, Comput. Math. Appl., 19, 53-62 (1990) · Zbl 0706.90074
[6] Al-Khayyal, F. A., Generalized bilinear programming: part i. models, applications and linear programming relaxation, Eur. J. Oper. Res., 60, 3, 306-314 (1992) · Zbl 0784.90051
[7] Audet, C.; Hansen, P.; Jaumard, B.; Savard, G., A symmetrical linear maxmin approach to disjoint bilinear programming, Math. Program., 85, 573-592 (1999) · Zbl 0980.90051
[8] Ban, X. J.; Lu, S.; Ferris, M.; Liu, H. X., Risk averse second best toll pricing, Transportation and Traffic Theory 2009: Golden Jubilee, 197-218 (2009), Springer US
[9] Bard, J. F., Practical Bilevel Optimization: Algorithms and Applications (1998), Kluwer Academic, Dordrecht · Zbl 0943.90078
[10] Brotcorne, L.; Labbe, M.; Marcotte, P.; Savard, G., A bilevel model for toll optimization on a multicommodity transportation network, Transp. Sci., 35, 4, 345-358 (2001) · Zbl 1069.90502
[11] C̆ervinka, M.; Matonoha, C.; Outrata, J. V., On the computation of relaxed pessimistic solutions to MPECs, Optim. Methods Software, 28, 186-206 (2013) · Zbl 1270.90071
[12] Charnes, A.; Cooper, W. W.; Thompson, G. L., Some properties of redundant constraints and extraneous variables in direct and dual linear programming problems, Oper. Res., 10, 711-723 (1962) · Zbl 0122.15302
[13] Colson, B.; Marcotte, P.; Savard, G., An overview of bilevel optimization, Ann. Oper. Res., 153, 235-256 (2007) · Zbl 1159.90483
[14] Dassanayaka, S., Methods of Variational Analysis in Pessimistic Bilevel Programming (2010), Phd thesis, Wayne State University
[15] Dempe, S., Foundations of Bilevel Programming, Nonconvex Optimization and its Applications Series (2002), Kluwer Academic, Dordrecht · Zbl 1038.90097
[16] Dempe, S., Annottated bibliography on bilevel programming and mathematical problems with equilibrium constraints, Optimization, 52, 333-359 (2003) · Zbl 1140.90493
[17] Dempe, S.; Mordukhovich, B. S.; Zemkoho, A. B., Necessary optimality conditions in pessimistic bilevel programming, Optimization, 63, 505-533 (2014) · Zbl 1302.90206
[18] Ding, X.; Al-Khayyal, F., Accelerating convergence of cutting plane algorithms for disjoint bilinear programming, J. Global Optim., 38, 3, 421-436 (2007) · Zbl 1171.90494
[19] Effati, S.; Mansoori, A.; Eshaghnezhad, M., An efficient projection neural network for solving bilinear programming problems, Neurocomputing, 168, 1188-1197 (2015)
[20] Falk, J. E., A linear max-min problem, Math. Program., 5, 1, 169-188 (1973) · Zbl 0276.90053
[21] Gallo, G.; Ülkücü, A., Bilinear programming: an exact algorithm, Math. Program., 12, 1, 173-194 (1977) · Zbl 0363.90086
[22] Gao, Y.; Zhang, G.; Lu, J.; Wee, H. M., Particle swarm optimization for bi-level pricing problems in supply chains, J. Global Optim., 51, 245-254 (2011) · Zbl 1230.90179
[23] Guo, X.; Hu, T.; Zhang, T.; Lv, Y., Bilevel model for multi-reservoir operating policy in inter-basin water transfer-supply project, J. Hydrol., 424, 252-263 (2012)
[24] Horst, R.; Tuy, H., Global Optimization: Deterministic Approaches (1996), Springer · Zbl 0867.90105
[25] Iyer, R. R.; Grossmann, I. E., A bilevel decomposition algorithm for long-range planning of process networks, Ind. Eng. Chem. Res., 37, 2, 474-481 (1998)
[26] Kalashnikov, V. V.; Dempe, S.; Përez-Valdës, G. A.; Kalashnykova, N. I.; Camacho-Vallejo, J. F., Bilevel programming and applications, Math. Prob. Eng. (2014)
[27] Konno, H., A cutting plane algorithm for solving bilinear programs, Math. Program., 11, 1, 14-27 (1976) · Zbl 0353.90069
[28] Lignola, M. B.; Morgan, J., Topological existence and stability for stackelberg problems, J. Optim. Theory Appl., 84, 145-169 (1995) · Zbl 0826.90148
[29] Liu, J.; Fan, Y. X.; Chen, Z.; Zheng, Y., Pessimistic bilevel optimization: a survey, Int. J. Comput. Intell. Syst., 11, 725-736 (2018)
[30] Loridan, P.; Morgan, J., New results on approximate solutions in two-level optimization, Optimization, 20, 819-836 (1989) · Zbl 0684.90089
[31] Loridan, P.; Morgan, J., ϵ-regularized two-level optimization problems: approximation and existence results, Proceeding of the Fifth French-German Optimization Conference, 99-113 (1989), Springer Berlin Heidelberg · Zbl 0688.90045
[32] Loridan, P.; Morgan, J., Weak via strong stackelberg problem: new results, J. Global Optim., 8, 263-287 (1996) · Zbl 0861.90151
[33] Lucchetti, R.; Mignanego, F.; Pieri, G., Existence theorems of equilibrium points in stackelberg games with constraints, Optimization, 18, 857-866 (1987) · Zbl 0638.90106
[34] Lu, J.; Han, J.; Hu, Y.; Zhang, G., Multilevel decision-making: a survey, Inf. Sci., 346-347, 463-487 (2016) · Zbl 1398.90077
[35] Marcotte, P.; Savard, G., Bilevel programming: a combinatorial perspective, Graph theory and combinatorial optimization, 191-217 (2005), Springer US · Zbl 1098.90059
[36] Marhfour, A., Mixed solutions for weak stackelberg problems: existence and stability results, J. Optim. Theory Appl., 105, 417-440 (2000) · Zbl 1050.91004
[37] Ritter, K., A method for solving maximum-problems with a nonconcave quadratic objective function, Zeitschrift fur Wahrscheinlichkeitstheorie und verwandte Gebiete, 4, 4, 340-351 (1966) · Zbl 0139.13105
[38] Rockafellar, R. T., Convex Analysis (1970), Princeton University Press, Princeton · Zbl 0229.90020
[39] Saranwong, S.; Likasiri, C., Product distribution via a bi-level programming approach: algorithms and a case study in municipal waste system, Expert Syst. Appl., 44, 78-91 (2016)
[40] Tsoukalas, A.; Wiesemann, W.; Rustem, B., Global optimisation of pessimistic bi-level problems, (Pardalos, P. M.; Coleman, T. F., Lectures on Global Optimization, Fields Institute Communications 55 (2009), Americal Mathematical Society, Providence), 215-243 · Zbl 1190.90148
[41] Sherali, H. D.; Alameddine, A., A new reformulation-linearization technique for bilinear programming problems, J. Global Optim., 4, 379-410 (1992) · Zbl 0791.90056
[42] Vaish, H.; Shetty, C. M., The bilinear programming problem, Nav. Res. Logist., 23, 2, 303-309 (1976) · Zbl 0349.90071
[43] Wiesemann, W.; Tsoukalas, A.; Kleniati, P.; Rustem, B., Pessimistic bi-level optimisation, SIAM J. Optim., 23, 353-380 (2013) · Zbl 1270.90088
[44] Zhang, G.; Zhang, G.; Gao, Y.; Lu, J., Competitive strategic bidding optimization in electricity markets using bilevel programming and swarm technique, IEEE Trans. Ind. Electron., 58, 2138-2146 (2011)
[45] Zhang, G.; Lu, J.; Gao, Y., Multi-level Decision Making: Models, Methods and Applications (2015), Springer, Berlin · Zbl 1308.91006
[46] Zhang, G.; Han, J.; Lu, J., Fuzzy bi-level decision-making techniques: a survey, Int. J. Comput. Intell. Systems, 9, 25-34 (2016)
[47] Zheng, Y.; Wan, Z.; Sun, K.; T., Z., An exact penalty method for weak linear bilevel programming problem, J. Appl. Math. Comput., 42, 41-49 (2013) · Zbl 1295.90020
[48] Zheng, Y.; Wan, Z.; Jia, S.; Wang, G., A new method for strong-weak linear bilevel programming problem, J. Indus. Manage. Optim., 11, 529-547 (2015) · Zbl 1304.90167
[49] Zheng, Y.; Fang, D.; Wan, Z., A solution approach to the weak linear bilevel programming problems, Optimization, 7, 1437-1449 (2016) · Zbl 1346.90760
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.