A Genetic Algorithm for Solving Linear Integer Bilevel Programming Problems

This manuscript discusses a class of linear integer bilevel programming problems, in which the objective functions and the constraints are linear. A genetic algorithm based on gradient information guidance is proposed for this kind of problems. First of all, for each fixed upper-level variable x, it is proved that the optimal solution y to the lowerlevel integer programming problem can be obtained by solving associated relaxed problems, and then a simplified branch and bound approach is used to solve the follower-level programming problems. In addition, a crossover operator based on gradient information guidance is designed, and the descendant individual is produced in the negative gradient direction of the upper-level function. The simulation results illustrate that the proposed algorithm is efficient and robust.