A genetic algorithm using a finite search space for solving nonlinear/linear fractional bilevel programming problems.

*(English)*Zbl 1332.90293Summary: The bilevel programming problem is strongly NP-hard and non-convex, which implies that the problem is very challenging for most canonical optimization approaches using single-point search techniques to find global optima. In the present paper, a class of nonlinear bilevel programming problems are considered where the follower is a linear fractional program. Based on a novel coding scheme, a genetic algorithm with global convergence was developed. First, potential bases of the follower’s problem were taken as individuals, and a genetic algorithm was used to explore these bases. In addition, in order to evaluate each individual, a fitness function was presented by making use of the optimality conditions of linear fractional programs. Also, the fitness evaluation, as a sub-procedure of optimization, can partly improve the leader’s objective. Finally, some computational examples were solved and the results show that the proposed algorithm is efficient and robust.

##### MSC:

90C32 | Fractional programming |

90C59 | Approximation methods and heuristics in mathematical programming |

Full Text:
DOI

##### References:

[1] | Abdou-Kandil, H; Bertrand, P, Government-private sector relations as a Stackelberg game: A degenerate case, Journal of Economic Dynamics and Control, 11, 513-517, (1987) · Zbl 0638.90021 |

[2] | Andreani, R; Castro, SLC; Chela, JL; Friedlande, A; Santos, SA, An inexact-restoration method for nonlinear bilevel programming problems, Computational Optimization and Applications, 43, 307-328, (2009) · Zbl 1170.90484 |

[3] | Arroyo, JM; Galiana, FD, On the solution of the bilevel programming formulation of the terrorist threat problem, IEEE Transactions on Power Systems, 20, 789-797, (2009) |

[4] | Bäck, T. (1996). Evolutionary algorithms in theory and practice. Oxford: Oxford University Press. · Zbl 0877.68060 |

[5] | Bard, J. F. (1998). Practical bilevel optimization: Algorithms and applications. Dordrecht: Kluwer Academic Publishers. · Zbl 0943.90078 |

[6] | Bard, JF; Plummer, JC; Sourie, JC, A bilevel programming approach to determining tax credits for biofuel production, European Journal of Operational Research, 120, 30-43, (2000) · Zbl 0976.90099 |

[7] | Ben-Ayed, O; Boyce, D; Blair, C, A general bilevel linear programming formulation of the network design problem, Transportation Research, 22B, 311-318, (1988) |

[8] | Calvete, HI; Gale, C, On the quasiconcave bilevel programming problem, Journal of Optimization Theory and Applications, 98, 613-622, (1998) · Zbl 0913.90240 |

[9] | Calvete, HI; Gale, C; Mateo, PM, A new approach for solving linear bilevel problems using genetic algorithms, European Journal of Operational Research, 188, 14-28, (2008) · Zbl 1135.90023 |

[10] | Calvete, HI; Gale, C; Mateo, PM, A genetic algorithm for solving linear fractional bilevel problems, Annals of Operations Research, 166, 39-56, (2009) · Zbl 1163.90759 |

[11] | Calvete, HI; Gale, C; Oliveros, M, Bilevel model for production-distribution planning solved by using ant colony optimization, Computers and Operations Research, 38, 320-327, (2011) · Zbl 1231.90158 |

[12] | Colson, B; Marcotte, P; Savard, G, An overview of bilevel optimization, Annals of Operations Research, 153, 235-256, (2007) · Zbl 1159.90483 |

[13] | Colson, B; Marcotte, P; Savard, G, A trust-region method for nonlinear bilevel programming: algorithm and computational experience, Computational Optimization and Applications, 30, 211-227, (2005) · Zbl 1078.90041 |

[14] | Deb, K; Sinha, A, An evolutionary approach for bilevel multi-objective problems, Communications in Computer and Information Science, 35, 17-24, (2009) |

[15] | Dempe, S, A simple algorithm for the linear bilevel programming problem, Optimization, 18, 373-385, (1987) · Zbl 0634.90075 |

[16] | Dempe, S. (2002). Foundations of bilevel programming. Dordrecht: Kluwer Academie Publishers. · Zbl 1038.90097 |

[17] | Dempe, S, Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52, 333-359, (2003) · Zbl 1140.90493 |

[18] | Dempe, S; Zemkoho, AB, Bilevel road pricing: theoretical analysis and optimality conditions, Annals of Operations Research, 196, 223-240, (2012) · Zbl 1274.90374 |

[19] | Etoa, JBE, Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming, Journal of Global Optimization, 47, 615-637, (2010) · Zbl 1237.90176 |

[20] | Etoa, JBE, Solving quadratic convex bilevel programming problems using a smoothing method, Applied Mathematics and Computation, 217, 6680-6690, (2011) · Zbl 1211.65070 |

[21] | Glackin, J; Ecker, JG; Kupferschmid, H, Solving bilevel linear programs using multiple objective linear programming, Journal of Optimization Theory and Applications, 140, 197-212, (2009) · Zbl 1163.90020 |

[22] | Gümüs, ZH; Floudas, CA, Global optimization of mixed-integer bilevel programming problems, Computational Management Science, 2, 181-212, (2005) · Zbl 1112.90061 |

[23] | Lan, KM; Wen, UP; Shih, HS, A hybrid neural network approach to bilevel programming problems, Applied Mathematics Letters, 20, 880-884, (2007) · Zbl 1162.90514 |

[24] | Li, H; Wang, Y, An interpolation-based genetic algorithm for solving nonlinear bilevel programming problems, Chinese Journal of Computers, 31, 910-918, (2008) |

[25] | Li, H; Wang, Y, Exponential distribution-based genetic algorithm for solving mixed-integer bilevel programming problems, Journal of Systems Engineering and Electronics, 19, 1159-1164, (2008) · Zbl 1228.90059 |

[26] | Li, H., & Wang, Y. (2011). A real-binary coded genetic algorithm for solving nonlinear bilevel programming with nonconvex objective functions. In The proceedings of 2011 IEEE congress on evolutionary computation (CEC) (pp. 2496-2500). New Orleans, USA. · Zbl 1170.90484 |

[27] | Mersha, AG; Dempe, S, Direct search algorithm for bilevel programming problems, Computational Optimization and Applications, 49, 1-15, (2011) · Zbl 1242.90240 |

[28] | Migdalas, A, Bilevel programming in traffic planning: models, methods and challenge, Journal of Global Optimization, 7, 381-405, (1995) · Zbl 0844.90050 |

[29] | Muu, LD; Quy, NV, A global optimization method for solving convex quadratic bilevel programming problems, Journal of Global Optimization, 26, 199-219, (2003) · Zbl 1053.90104 |

[30] | Shim, Y; Fodstad, M; Gabriel, SA; Tomasgard, A, A branch-and-bound method for discretely-constrained mathematical programs with equilibrium constraints, Annals of Operations Research, 210, 5-31, (2013) · Zbl 1288.90111 |

[31] | Swarup, K, Linear fractional functional programming, Operations Research, 13, 1029-1036, (1965) · Zbl 0132.13802 |

[32] | Scaparra, MP; Church, RL, A bilevel mixed-integer program for critical infrastructure protection planning, Computers and Operations Research, 35, 1905-1923, (2008) · Zbl 1139.90439 |

[33] | Wang, G; Zhu, K; Wan, Z, An approximate programming method based on the simplex method for bilevel programming problem, Computers and Mathematics with Applications, 59, 3355-3360, (2010) · Zbl 1198.90363 |

[34] | Wang, Y; Jiao, YC; Li, H, An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 35, 221-232, (2005) |

[35] | Wang, Y; Li, H; Dang, C, A new evolutionary algorithm for a class of nonlinear bilevel programming problems and its global convergence, INFORMS Journal on Computing, 23, 618-629, (2011) · Zbl 1243.90208 |

[36] | Wang, Y. (2011). Theory and methodology of evolutionary computation. Beijing: Science Press. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.