Due to 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 the exactness of our methods are provided. To assess the performance of the presented methods, we perform an extensive computational study on 2240 instances. We observe that the optimality gap is closed for a significant portion of the considered instances. Moreover, for the special case of Γ-robust interdiction problems, we report considerable speed-up factors when compared to recently published problem-tailored and exact solution approaches while also solving more instances to global optimality.
Article
View Heuristic Methods for Mixed-Integer, Linear, and Γ-Robust Bilevel Problems