Heuristic Methods for Γ-Robust Mixed-Integer Linear Bilevel Problems

Because of their nested structure, bilevel problems are intrinsically hard to solve—even if all variables are continuous and all parameters of the problem are exactly known. In this paper, we study mixed-integer linear bilevel problems with lower-level objective uncertainty, which we address using the notion of Γ-robustness. To tackle the Γ-robust counterpart of the bilevel problem, we present heuristic methods that are based on the solution of a linear number of problems of the nominal type. Moreover, quality guarantees for heuristically obtained solutions as well as sufficient ex-post conditions for global optimality of the outcomes are provided. In an extensive computational study on 2,240 instances, we assess the performance of our heuristics and compare them with alternative methods—both heuristic and exact—from the literature. We observe that the optimality gap is closed for a significant portion of the considered instances and that our methods often practically outperform alternative approaches in terms of the solution quality. Moreover, for the special case of Γ-robust interdiction problems, we report considerable speed-up factors when compared with recently published problem-tailored and exact solution approaches while also solving more instances to global optimality.