An Effective Branch-and-cut algorithm in Order to Solve the Mixed Integer Bi-level Programming


  • Arsalan Rahmani University of Kurdistan
  • Majid Yousefikhoshbakht Islamic Azad University



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.


Download data is not yet available.

Author Biography

Arsalan Rahmani, University of Kurdistan

Department of Mathematics


Achterberg, T., Koch, T., Martin, A. (2005). Branching rules revisited. Operations Research Letters, 33(1), 42-54.

Colson, B., Marcotte, P., Savard, G. (2005). Bilevel programming: A survey. 4OR, 3(2), 87-107.

Bard, J.F., Falk, J.E. (1982). An explicit solution to the multi-level programming problem. Computer and Operations Research, 9(1), 77-100.

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.

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.

Beresnev, V.L. (2013). Branch-and-bound algorithm for a competitive facility location problem. Computers & Operations Research, 40(8), 2062-2070.

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.

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.

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.

Jeroslow, R.G. (1985). The polynomial hierarchy and a simple model for competitive analysis. Mathematical Programming, 32(2), 146-164.

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.

Pistikopoulos, E.N, Georgiadis, M.C, Dua, V. (2007). Multi-Parametric Programming: Theory, Algorithms, and Applications, Volume 1, Weinheim: Wiley-VCH, 1.

Rahmani, A., Mirhassani, S. A. (2015). Lagrangean relaxation-based algorithm for bi-level problems. Optimization Methods and Software, 30(1), 1-14.

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.

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.

Vicente, J., Savard, L., Judice, G. (1996). Discrete Linear Bilevel Programming Problem. Journal of Optimization Theory and Applications, 89(3) 597-614.

Wen, U., Yang. Y. (1990). Algorithms for solving the mixed integer two-level linear programming problem. Computers & Operations Research, 17(2), 133-142.




How to Cite

Rahmani, A., & Yousefikhoshbakht, M. (2017). An Effective Branch-and-cut algorithm in Order to Solve the Mixed Integer Bi-level Programming. International Journal of Production Management and Engineering, 5(1), 1–10.