Abstract
Most real-world optimization problems are hierarchical involving non-cooperative objectives. Many of these problems can be formulated in terms of the first (upper level) objective function being minimized over the solution set mapping of the second (lower level) optimization problem. Often the upper level decision maker is risk-averse. The resulting class of problem is named weak bilevel programming problem. This paper presents a new algorithm which embeds a penalty function method into a branch and bound algorithm to deal with a weak linear bilevel programming problem. An example illustrates the feasibility of the proposed algorithm.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bard J F. Practical Bilevel Optimization: Algorithms and Applications [M]. Dordrecht: Kluwer Academic, 1998.
Dempe S. Foundations of Bilevel Programming, Nonconvex Optimization and Its Applications Series [M]. Dordrecht: Kluwer Academic, 2002.
Zhang G, Lu J, Gao Y. Multi–Level Decision Making: Models, Methods and Applications [M]. Berlin: Springer–Verlag, 2015.
Dempe S. Annottated bibliography on bilevel programming and mathematical problems with equilibrium constraints [J]. Optimization, 2003, 52: 333–359.
Colson B, Marcotte P, Savard G. An overview of bilevel optimization [J]. Annals of Operations Research, 2007, 153: 235–256.
Lu J, Han J, Hu Y, et al. Multilevel decision–making: A survey [J]. Information Sciences, 2016, 346: 463–487.
Liu J, Fan Y, Chen Z, et al. Pessimistic bilevel optimization: A survey [J]. International Journal of Computational Intelligence Systems, 2018, 11: 725–736.
Loridan P, Morgan J. Weak via strong Stackelberg problem: New results [J]. Journal of Global Optimization, 1996, 8: 263–287.
Wiesemann W, Tsoukalas A, Kleniati P, et al. Pessimistic bi–level optimization [J]. SIAM Journal on Optimization, 2013, 23: 353–380.
Aboussoror A, Mansouri A. Existence of solutions to weaknonlinear bilevel problems via MinSup and d.c. problems. RAIRO Operations Research, 2008, 42: 87–103.
Aboussoror A, Adly S, Jalby V. Weak nonlinear bilevel problems: Existence of solutions via reverse convex and convex maximization problems [J]. Journal of Industrial and Management Optimization, 2011, 7: 559–571.
Lignola M B, Morgan J. Topological existence and stability for Stackelberg problems [J]. Journal of Optimization Theory and Applications, 1995, 84: 145–169.
Loridan P, Morgan J. New results on approximate solutions in two–level optimization [J]. Optimization, 1989, 20(6): 819–836.
Lucchetti R, Mignanego F, Pieri G. Existence theorems of equilibrium points in Stackelberg games with constraints [J]. Optimization, 1987, 18: 857–866.
Lignola M B, Morgan J. Inner regularizations and viscosity solutions for pessimistic bilevel optimization problems [J]. Journal of Optimization Theory and Applications, 2017, 173(1): 183–202.
Dassanayaka S. Methods of Variational Analysis in Pessimistic Bilevel Programming [D]. Detroit: Wayne State University, 2010.
Dempe S, Mordukhovich B S, Zemkoho A B. Necessary optimality conditions in pessimistic bilevel programming [J]. Optimization, 2014, 63: 505–533.
Cervinka M, Matonoha C, Outrata J V. On the computation of relaxed pessimistic solutions to MPECs[J]. Optimization Methods and Software, 2013, 28: 186–206.
Aboussoror A, Mansouri A. Weak linear bilevel programming problems: Existence of solutions via a penalty method [J]. Journal of Mathematical Analysis and Applications, 2005, 304: 399–408.
Zheng Y, Wan Z P, Sun K, et al. An exact penalty method for weak linear bilevel programming problem [J]. Journal of Applied Mathematics and Computing, 2013, 42: 41–49.
Zheng Y, Fang D, Wan Z P. A solution approach to the weak linear bilevel programming problems [J]. Optimization, 2016, 7: 1437–1449.
Zheng Y, Zhuo X, Chen J. Maximum entropy approach for solving pessimistic bilevel programming problems [J]. Wuhan University Journal of Natural Sciences, 2017, 22(1): 63–67.
Zeng B. Easier than We Thought—A Practical Scheme to Compute Pessimistic Bilevel Optimization Problem[R]. Pittsburgh: University of Pittsburgh, 2015.
Fortuny–Amat J, McCarl B. A representation and economic interpretation of a two–level programming problem [J]. Journal of the Operational Research Society, 1981, 32(9): 783–792.
Bard J F, Moore J T. A branch and bound algorithm for the bilevel programming problem [J]. SIAM Journal on Scientific and Statistical Computing, 1990, 11: 281–292.
Hansen P, Jaumard B, Savard G. New branch–and–bound rules for linear bilevel programming [J]. SIAM Journal on Scientific and Statistical Computing, 1992, 13: 1194–1217.
Liu G S, Zhang J Z. A new branch and bound algorithm for solving quadratic programs with linear complementarity constraints [J]. Journal of Computational and Applied Mathematics, 2002, 146: 77–87.
Farvaresh H, Sepehri M M. A branch and bound algorithm for bi–level discrete network design problem [J]. Networks and Spatial Economics, 2013, 13: 67–106.
Shim Y, Fodstad M, Gabriel S A, et al. A branch–and–bound method for discretely–constrained mathematical programs with equilibrium constraints [J]. Annals of Operations Research, 2013, 210: 5–31.
Tawarmalani M, Sahinidis N V. A polyhedral branchand–cut approach to global optimization [J]. Mathematical Programming, 2005, 103(2): 225–249.
Wan Z P, Wang G M, Sun B. A hybrid intelligent algorithm by combining particle swarm optimization with chaos searching technique for solving nonlinear bilevel programming problems [J]. Swarm and Evolutionary Computation, 2013, 8: 26–32.
Wan Z P, Mao L, Wang G M. Estimation of distribution algorithm for a class of nonlinear bilevel programming problems [J]. Information Sciences, 2014, 256: 184–196.
Liu G S, Xu S, Han J. A trust region algorithm for solving bilevel programming problems [J]. Acta Mathematicae Applicatae Sinica, English Series, 2013, 29: 491–498.
Author information
Authors and Affiliations
Corresponding author
Additional information
Foundation item: Supported by the National Natural Science Foundation of China (11501233), and the Natural Science Research Project of Universities of Anhui Province (KJ2018A0390)
Rights and permissions
About this article
Cite this article
Liu, J., Hong, Y. & Zheng, Y. A Branch and Bound-Based Algorithm for the Weak Linear Bilevel Programming Problems. Wuhan Univ. J. Nat. Sci. 23, 480–486 (2018). https://doi.org/10.1007/s11859-018-1352-8
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11859-018-1352-8