  In this work we propose an improvement of the $x$-space algorithm developed
for solving a class of min--max bilevel optimization problems (Tang Y., Richard
J.P.P., Smith J.C. (2016), A class of algorithms for mixed-integer bilevel
min--max optimization. Journal of Global Optimization, 66(2), 225--262). In
this setting, the leader of the upper level problem aims at restricting the
follower's decisions by minimizing an objective function, which the follower
intends to maximize in the lower level problem by making decisions still
available to her. The $x$-space algorithm solves upper and lower bound problems
consecutively until convergence, and requires the dualization of an
approximation of the follower's problem in formulating the lower bound problem.
We first reformulate the lower bound problem using the properties of an optimal
solution to the original formulation, which makes the dualization step
unnecessary. The reformulation makes possible the integration of a greedy
covering heuristic into the solution scheme, which results in a considerable
increase in the efficiency. The new algorithm referred to as the improved
$x$-space algorithm is implemented and applied to a recent min--max bilevel
optimization problem that arises in the context of reducing the misinformation
spread in social networks. It is also assessed on the benchmark instances of
two other bilevel problems: zero-one knapsack problem with interdiction and
maximum clique problem with interdiction. Numerical results indicate that the
performance of the new algorithm is superior to that of the original algorithm,
and also compares favorably with a recent algorithm developed for mixed-integer
bilevel linear programs.
