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

Arsalan Rahmani, Majid Yousefikhoshbakht


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.


Mixed-integer bi-level programming; Branch and cut method; Fathoming branch

Full Text:



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.

Abstract Views

Metrics Loading ...

Metrics powered by PLOS ALM


Cited-By (articles included in Crossref)

This journal is a Crossref Cited-by Linking member. This list shows the references that citing the article automatically, if there are. For more information about the system please visit Crossref site

1. Maintenance priorities determination for a repairable unit of a sugar plant
Gaurav Sharma, P C Tewari
Journal of Physics: Conference Series  vol: 1240  first page: 012032  year: 2019  
doi: 10.1088/1742-6596/1240/1/012032

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives- 4.0 International License 

Universitat Politècnica de València

e-ISSN: 2340-4876     ISSN: 2340-5317