In this work we propose a solution method based on Lagrange relaxation for discrete-continuous bi-level problems, with binary variables in the leading problem, considering the optimistic approach in bi-level programming. For the application of the method, the two-level problem is reformulated using the Karush-Kuhn-Tucker conditions. The resulting model is linearized taking advantage of the structure of the leading problem. Using a Lagrange relaxation algorithm, it is possible to find a global solution efficiently. The algorithm was tested to show how it performs.
References
[1]
Von Stackelberg, H. (1934) Marktform und gleichgewicht. Springer, Berlin.
[2]
Colson, B., Marcotte, P. and Savard, G. (2007) An Overview of Bilevel Optimization. Annals of Operations Research, 153, 235-256.
https://doi.org/10.1007/s10479-007-0176-2
[3]
Ben-Ayed, O. and Blair, C.E. (1990) Computational Difficulties of Bilevel Linear Programming. Operations Research, 38, 556-560.
https://doi.org/10.1287/opre.38.3.556
[4]
Moore, J.T. and Bard, J.F. (1990) Mixed Integer Linear Bilevel Programming Problem. Operations Research, 38, 911-921. https://doi.org/10.1287/opre.38.5.911
[5]
Wen, U.P. and Yang, Y.H. (1990) Algorithms for Solving the Mixed Integer Two-Level Linear Programming Problem. Computers and Operations Research, 17, 133-142.
https://doi.org/10.1016/0305-0548(90)90037-8
[6]
Bard, J.F. and Moore, J.T. (1992) An Algorithm for the Discrete Bilevel Programming Problem. Naval Research Logistics, 39, 419-435.
https://doi.org/10.1002/1520-6750(199204)39:3<419::AID-NAV3220390310>3.0.CO;2-C
[7]
Edmunds, T.A. and Bard, J.F. (1992) An Algorithm for the Mixed-Integer Nonlinear Bilevel Programming Problem. Annals of Operations Research, 34, 149-162.
https://doi.org/10.1007/BF02098177
[8]
Dempe, S. (2003) Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints. Optimization, 52, 333-359.
https://doi.org/10.1080/0233193031000149894
[9]
Vicente, L., Savard, G. and Judice, J. (1996) Discrete Linear Bilevel Programming Problem. Journal of Optimization Theory and Applications, 89, 597-614.
https://doi.org/10.1007/BF02275351
[10]
Ko, C.A. (2005) Global Optimization of Mixed-Integer Bilevel Programming Problems. Computational Management Science, 2, 181-212.
https://doi.org/10.1007/s10287-005-0025-1
[11]
Faísca, N.P., Dua, V., Rustem, B., Saraiva, P.M. and Pistikopoulos, E.N. (2007) Parametric Global Optimisation for Bilevel Programming. Journal of Global Optimization, 38, 609-623. https://doi.org/10.1007/s10898-006-9100-6
[12]
Domínguez, L.F. and Pistikopoulos, E.N. (2010) Multiparametric Programming Based Algorithms for Pure Integer and Mixed-Integer Bilevel Programming Problems. Computers and Chemical Engineering, 34, 2097-2106.
https://doi.org/10.1016/j.compchemeng.2010.07.032
[13]
Köppe, M., Queyranne, M. and Ryan, C.T. (2010) Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs. Journal of Optimization Theory and Applications, 146, 137-150. https://doi.org/10.1007/s10957-010-9668-3
[14]
Mitsos, A. (2010) Global Solution of Nonlinear Mixed-Integer Bilevel Programs. Journal of Global Optimization, 47, 557-582.
https://doi.org/10.1007/s10898-009-9479-y
[15]
Xu, P. and Wang, L. (2014) An Exact Algorithm for the Bilevel Mixed Integer Linear Programming Problem under Three Simplifying Assumptions. Computers and Operations Research, 41, 309-318. https://doi.org/10.1016/j.cor.2013.07.016
[16]
Sharma, V., Dahiya, K. and Verma, V. (2014) A Class of Integer Linear Fractional Bilevel Programming Problems. Optimization, 63, 1565-1581.
https://doi.org/10.1080/02331934.2014.883509
[17]
Saharidis, G.K. and Ierapetritou, M.G. (2009) Resolution Method for Mixed Integer Bi-Level Linear Problems Based on Decomposition Technique. Journal of Global Optimization, 44, 29-51. https://doi.org/10.1007/s10898-008-9291-0
[18]
Fontaine, P. and Minner, S. (2014) Benders Decomposition for Discrete-Continuous Linear Bilevel Problems with Application to Traffic Network Design. Transportation Research Part B: Methodological, 70, 163-172.
https://doi.org/10.1016/j.trb.2014.09.007
[19]
Caramia, M. and Mari, R. (2015) A Decomposition Approach to Solve a Bilevel Capacitated Facility Location Problem with Equity Constraints. Optimization Letters, 10, 997-1019.
[20]
Rahmani, A. and MirHassani, S.A. (2015) Lagrangean Relaxation-Based Algorithm for Bi-Level Problems. Optimization Methods and Software, 30, 1-14.
https://doi.org/10.1080/10556788.2014.885519
[21]
Dempe, S. (2002) Foundations of Bilevel Programming. Springer Science & Business Media, Berlin.
[22]
Bard, J.F. (1998) Practical Bilevel Optimization: Algorithms and Applications, Volume 30. Springer Science & Business Media, Berlin.
[23]
Cao, D. and Chen, M.Y. (2006) Capacitated Plant Selection in a Decentralized Manufacturing Environment: A Bilevel Optimization Approach. European Journal of Operational Research, 169, 97-110. https://doi.org/10.1016/j.ejor.2004.05.016
Nowak, I. (2006) Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming, Volume 152. Springer Science & Business Media, Berlin.
[26]
De Haro, S.C.L., Galán, A.R. and Moreno, A.B. (2004) Modelado de algoritmos de descomposición con gams.
[27]
Tuy, H. and Ghannadan, S. (1998) A New Branch and Bound Method for Bilevel Linear Programs. In: Multilevel Optimization: Algorithms and Applications, Springer, Berlin, 231-249. https://doi.org/10.1007/978-1-4613-0307-7_10
