(568e) A Branch and Bound Algorithm for Discrete Bilevel Optimization

Bilevel optimization problems arise in situations where two independent decision-makers choose their actions sequentially with the goal of optimizing their own objective functions. Bilevel optimization problems are known to yield solutions corresponding to Stackelberg equilibria of extensive games with perfect information. The main characteristic of these games is that both players, leader and follower, are considered rational decision-makers that can predict and observe the actions of the opponent. In particular, the leader is aware the decision criterion and the constraints of the follower when choosing its actions, and the follower observes the actions of the leader before making its decisions.

A bilevel optimization problem can be described as a mathematical program with an optimization problem in the constraints. In general, bilevel optimization problems are very challenging because their feasible region is noncovex; however, for the case in which the lower-level problem is a linear program (LP), some reformulation methods have proved to be successful to solve them. These methods replace the lower-level problem with a set of constraints that only allows optimal responses of the follower to be feasible in the reformulation. In particular, two equivalent reformulation methods have shown to be effective: KKT reformulation and duality-based reformulation.

The reformulation methods used for bilevel optimization with LP lower level rely on their necessary and sufficient conditions for optimality. However, for the case in which the lower-level problem contains discrete variables, these reformulations are no longer valid. Some search procedures have been proposed to solve bilevel optimization problems with discrete variables in the lower level, but most of them are based on implicit enumeration schemes that are only effective for small-scale problems.

This research proposes a solution algorithm that explores the decision space of the leader using branch and bound, and identifies regions of the leader’s feasible region that imply the same reaction of the follower. Using this method, large regions of the leader’s decision space can be characterize by solving few Mixed-Integer Linear Programs (MILPs). The branch and bound scheme is efficient because at each node defining a subregion of the leader’s decision space, an upper and lower bound can be found. These bounds can be used to fathom subregions that do not contain the bilevel optimal solution before they are completely characterized.

The branch and bound algorithm is used to solve two small examples that illustrate how the feasible regions are explored and the bilevel optimal solutions are identified. Additionally, the algorithm is used to solve randomly generated instances of different sizes. The results show that the proposed branch and bound scheme solves small and middle-sized instances in reasonable computational times.