New branch-and-bound rules for linear bilevel programming.

*(English)*Zbl 0760.65063The authors propose a new depth-first branch and bound algorithm for linear bilevel programming. Necessary optimality conditions, expressed in terms of tightness of constraints in the followerâ€™s subproblem are derived. These conditions on the tightness are used to derive the branching rules.

With the help of two linear programming relaxations rejection rules are developed. The algorithm is illustrated by an example. Computational experience is reported for problems with up to 150 constraints, 250 variables controlled by the leader, and 150 variables controlled by the follower.

Reviewer: J.Terno (Dresden)

##### MSC:

65K05 | Mathematical programming (numerical methods) |

90C27 | Combinatorial optimization |

91A35 | Decision theory for games |

90B50 | Management decision making, including multiple objectives |

91B06 | Decision theory |