An Effective Branch-and-cut algorithm in Order to Solve the Mixed Integer Bi-level Programming
Keywords:Mixed-integer bi-level programming, Branch and cut method, Fathoming branch
In this paper, a new branch-and-cut algorithm for mixed integer bi-level programming is proposed. For achieving this purpose, a historical perspective of the development of enumeration methods in the field of bi-level linear programming is considered. Then, we present some obstacles for using branch and bound method based on them, and an algorithm is developed to solve for mixed integer bi-level problem. Finally, we use a preference function to determine the choice of branching and specialized cuts in a branch and cut tree. Computational results are reported and compared favorably to those of previous methods and then implications discussed. The results show that not only the proposed algorithm can find high quality solutions for solving a number of the problems, but also it is competitive with other famous published algorithms.
Achterberg, T., Koch, T., Martin, A. (2005). Branching rules revisited. Operations Research Letters, 33(1), 42-54. https://doi.org/10.1016/j.orl.2004.04.002
Colson, B., Marcotte, P., Savard, G. (2005). Bilevel programming: A survey. 4OR, 3(2), 87-107. https://doi.org/10.1007/s10288-005-0071-0
Bard, J.F., Falk, J.E. (1982). An explicit solution to the multi-level programming problem. Computer and Operations Research, 9(1), 77-100. https://doi.org/10.1016/0305-0548(82)90007-7
Bard, J.F., Moore, J.T.A. (1990). A branch and bound algorithm for the bilevel programming problem. SIAM Journal on Scientific and Statistical Computing, 11(2), 281-292. https://doi.org/10.1137/0911017
Beresnev, V.L. (2009). Upper Bounds for Objective Functions of Discrete Competitive Facility Location Problems. Journal of Applied and Industrial Mathematics, 3(4), 419-432. https://doi.org/10.1134/S1990478909040012
Beresnev, V.L. (2013). Branch-and-bound algorithm for a competitive facility location problem. Computers & Operations Research, 40(8), 2062-2070. http://dx.doi.org/10.1016/j.cor.2013.02.023
Beresnev, V.L., Melnikov, A.A. (2014). Branch-and-bound method for the competitive facility location problem with prescribed choice of suppliers, Diskretn. Anal. Issled. Oper., 21(2), 3-23.
Dempe, S. (2001). Discrete bilevel optimization problems. Technical Report D-04109, Institut fur Wirtschaftsinformatik, Universitat Leipzig, Leipzig, Germany.
Denegre, S., Ralphs, T.K. (2009). A Branch-and-Cut Algorithm for Bilevel Integer Programming. In Proceedings of the 11th INFORMS Computing Society Meeting, 65-78.
Domínguez, L.F., Pistikopoulos, E.N. (2010). Multiparametric programming based algorithms for pure integer and mixed-integer bilevel programming problems. Computers and Chemical Engineering, 34(12), 2097-2106. https://doi.org/10.1016/j.compchemeng.2010.07.032
Floudas, C.A., Pardalos, P.M., Adjiman, C., Esposito, W.R., Gümüş, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C. A. (2013). Handbook of test problems in local and global optimization (Vol. 33). Springer Science & Business Media.
Gümüş, Z.H., Floudas, F. (2005). Global optimization of mixed-integer bilevel programming problem. Computational Management Science, 2(3), 181-212. https://doi.org/10.1007/s10287-005-0025-1
Hansen, P., Jaumard, B., Savard, G. (1992). New branch-and-bound rules for linear bilevel programming. SIAM Journal on Scientific and Statistical Computing, 13(5), 1194-1217. https://doi.org/10.1137/0913069
Jeroslow, R.G. (1985). The polynomial hierarchy and a simple model for competitive analysis. Mathematical Programming, 32(2), 146-164. https://doi.org/10.1007/BF01586088
Mirhassani, S.A., Raeisi, S., Rahmani, A. (2015). Quantum binary particle swarm optimization-based algorithm for solving a class of bi-level competitive facility location problems. Optimization Methods and Software, 30(4), 756-768. https://doi.org/10.1080/10556788.2014.973875
Pistikopoulos, E.N, Georgiadis, M.C, Dua, V. (2007). Multi-Parametric Programming: Theory, Algorithms, and Applications, Volume 1, Weinheim: Wiley-VCH, 1. https://doi.org/10.1002/9783527631216
Rahmani, A., Mirhassani, S. A. (2015). Lagrangean relaxation-based algorithm for bi-level problems. Optimization Methods and Software, 30(1), 1-14. https://doi.org/10.1080/10556788.2014.885519
Shi, C., Lu, J., Zhang, G., Zhou, H. (2006). An Extended Branch and Bound Algorithm for Linear Bilevel Programming. Applied Mathematics and Computation, 180(2), 529-537. https://doi.org/10.1016/j.amc.2005.12.039
Vicente, L. (2001). Bilevel programming: Introduction, history and overview. In C. A. Floudas and P. M. Pardalos (eds.) Encyclopedia of optimization, 178-180. Springer: US. https://doi.org/10.1007/0-306-48332-7_38
Vicente, J., Savard, L., Judice, G. (1996). Discrete Linear Bilevel Programming Problem. Journal of Optimization Theory and Applications, 89(3) 597-614. https://doi.org/10.1007/BF02275351
Wen, U., Yang. Y. (1990). Algorithms for solving the mixed integer two-level linear programming problem. Computers & Operations Research, 17(2), 133-142. https://doi.org/10.1016/0305-0548(90)90037-8
How to Cite
This work as of Vol. 11 Iss. 2 (2023) is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike- 4.0 International License