Abstract
In this article, we propose a new algorithm for the resolution of mixed integer bi-level linear problem (MIBLP). The algorithm is based on the decomposition of the initial problem into the restricted master problem (RMP) and a series of problems named slave problems (SP). The proposed approach is based on Benders decomposition method where in each iteration a set of variables are fixed which are controlled by the upper level optimization problem. The RMP is a relaxation of the MIBLP and the SP represents a restriction of the MIBLP. The RMP interacts in each iteration with the current SP by the addition of cuts produced using Lagrangian information from the current SP. The lower and upper bound provided from the RMP and SP are updated in each iteration. The algorithm converges when the difference between the upper and lower bound is within a small difference ε. In the case of MIBLP Karush–Kuhn–Tucker (KKT) optimality conditions could not be used directly to the inner problem in order to transform the bi-level problem into a single level problem. The proposed decomposition technique, however, allows the use of KKT conditions and transforms the MIBLP into two single level problems. The algorithm, which is a new method for the resolution of MIBLP, is illustrated through a modified numerical example from the literature. Additional examples from the literature are presented to highlight the algorithm convergence properties.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bard J.F. (1983). An efficient point algorithm for a linear two-stage optimization problem. Oper. Res. 31(4): 670–684
Bard J.F. (1984). An investigation of the linear tree level programming problem. IEEE Trans. Syst. Man Cybern. 14: 711–717
Bard J.F. and Moore J.T. (1990). A branch and bound algorithm for the bilevel programming problem. SIAM J. Sci. Stat. Comp. 11: 281–292
Benders J.F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4: 238–252
Bialas, W., Karwan, M.: Multilevel linear programming. Technical Report 78-1, State University of New York at Buffalo, Operations Research Program (1978)
Bilias, W., Karwan, M., Shaw, J.: A parametric complementary pivot approach for two-level linear programming. Technical Report 80-2, State University of New York at Buffalo, Operations Research Program (1980)
Candler W. and Townsley R. (1982). A linear two-level programming problem. Comput. Oper. Res. 9: 59–76
Chen, Y., Florian, M.: On the geometry structure of linear bilevel programs: a dual approach. Technical Report CRT-867, Centre de recherche sur les Transports (1992)
Dempe, S.: Discrete bi-level optimization problems. http://www.mathe.tufreiberg.de/dempe, TU Chemnizt (1995)
Faisca N., Dua V., Rustem B., Saraiva P.M. and Pistikopoulos E.N. (2007). Parametric global optimization for bi-level programming. J. Glob. Optim. 38(4): 609–623
Floudas C.A. (1995). Nonlinear and Mixed-Integer Optimization, Fundamentals and Applications. Oxford University Press, Oxford, New York
Floudas C.A., Gümus Z.H. and Ierapetritou M.G. (2001). Global optimization in design under uncertainty feasibility test and flexibility index problems. Ind. Eng. Chem. Res. 40: 4267–4282
Foteinou, P., Yang, E., Sacharidis, G.K., Ierapetritou, M.G., Androulakis, I.P.: A mixed integer optimization framework for the synthesis and analysis of regulatory networks. To appear in JOGO (2008)
Grossmann I.E. and Floudas C.A. (1987). Active constraint strategy for flexibility analysis in chemical processes. Comput. Chem. Eng. 11: 675
Gümus Z.H. and Floudas C.A. (2005). Global optimization of mixed-integer bilevel programming problems. Comput. Manag. Sci. 2: 181–212
Hansen P., Jaumard B. and Savard G. (1992). New branch-and-bound rules for linear bi-level programming. SIAM J. Sci. Stat. Comput. 13: 1194–1217
Haurie A., Savard G. and White D. (1990). A note on: an efficient point algorithm for a linear two stage optimization problem. Oper. Res. 38: 553–555
Marcotte P. and Zhu D.L. (1996). Exact and inexact penalty methods for the generalized bi-level programming problem. Math. Program. 74: 141–157
Minoux, M.: Mathematical Programming Theory and Algorithms. Wiley-Interscience Series in Discrete Mathematics and Optimization (1986)
Moore J.T. and Bard J.F. (1990). The mixed integer linear bi-level programming problem. Oper. Res. 38: 5
Papavassilopoulos, G.: Algorithms for static Stachelberg games with linear costs and polyhedral constraints. In: Proceeding of the 21st IEEE Conference on Decisions and control, pp. 647–652 (1982)
Sacharidis, G.K., Minoux, M., Ierapetritou, M.: Accelerating Benders decomposition using covering cut bundles generation. submitted (2008)
Savard, G.: Contributions à la programmation mathématique a deux niveaux. PhD thesis, Universite de Montreal, Ecole Polytechnique (1989)
Shi C., Lu J. and Zhang G. (2005). An extended Kuhn–Tucker approach for linear bi-level programming. Appl. Math. Comput. 162: 51–63
Shi C., Lu J., Zhang G. and Zhou H. (2006). An extended branch and bound algorithm for linear bilevel programming. Appl. Math. Comput. 180: 529–537
Tuy, H.: Handbook of applied optimization Panos M. Pardalos and Mauricion G.C. Resende chapter 12 Hierarchical optimization. Oxford University Press (2002)
Tuy H., Migdalas A. and Varbrand P. (1993). A global optimization approach for the linear two-level programs. J. Glob. Optim. 3: 1–23
Vincente L., Savard G. and Judice J. (1996). The discrete linear bi-level programming problem. J. Optim. Theory Appl. 89: 597–614
Visweswaran V., Floudas C.A., Ierapetritou M.G., Pistikopoulos E.N. (1996). A decomposition based global optimization approach for bi-level convex programming problems. In: Floudas C.A., Pardalos P.M. (eds). State of the Art in Global Optimization: Computational Methods and Applications, Book Series on Nonconvex Optimization and Its Applications. Kluwer Academic Publisher Printed in the Netherlands, pp. 139–162
Wang, G., Wan, Z., Wang, X.: Solving method for a class of bi-level linear programming based on genetic algorithms. Proceedings of PDCAT conference (2005)
Wen U.P. and Yang Y.H. (1990). Algorithms for solving the mixed integer two level linear programming problem. Comput. Op. Res. 17: 133–142
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Saharidis, G.K., Ierapetritou, M.G. Resolution method for mixed integer bi-level linear problems based on decomposition technique. J Glob Optim 44, 29–51 (2009). https://doi.org/10.1007/s10898-008-9291-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-008-9291-0