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

Arsalan Rahmani; Majid Yousefikhoshbakht

doi:10.4995/ijpme.2017.6512

Authors

Arsalan Rahmani University of Kurdistan
Majid Yousefikhoshbakht Islamic Azad University

DOI:

https://doi.org/10.4995/ijpme.2017.6512

Keywords:

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

Abstract

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.

Downloads

Download data is not yet available.

Author Biography

Arsalan Rahmani, University of Kurdistan

Department of Mathematics

References

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