A Value-Function-Based Exact Approach for the Bilevel Mixed-Integer Programming Problem

We examine bilevel mixed‐integer programs whose constraints and objective functions depend on both upper‐ and lower‐level variables. The class of problems we consider allows for nonlinear terms to appear in both the constraints and the objective functions, requires all upper‐level variables to be integer, and allows a subset of the lower‐level variables to be integer. This class of bilevel problems is difficult to solve because the upper‐level feasible region is defined in part by optimality conditions governing the lower‐level variables, which are difficult to characterize because of the nonconvexity of the follower problem. We propose an exact finite algorithm for these problems based on an optimal‐value‐function reformulation. We demonstrate how this algorithm can be tailored to accommodate either optimistic or pessimistic assumptions on the follower behavior. Computational experiments demonstrate that our approach outperforms a state‐of‐the‐art algorithm for solving bilevel mixed‐integer linear programs.