Title
On Local Search in Bilevel Mixed-Integer Linear Programming
Abstract
Local search in bilevel mixed-integer programming faces two major challenges: (i ) similarly
to many combinatorial optimization problems, local search requires an exponential number of improving
steps to converge in the worst case, and (ii ) evaluating the leader’s objective function requires solving the
follower’s problem, which may be hard by itself. We address the first challenge by extending the notion
of ε-local optimality—a generalization of local optimality—to the bilevel setting. To overcome the second
challenge, we introduce the concept of weak local optimality, yet another generalization. Specifically,
instead of computing the follower’s fully rational response, we evaluate the leader’s objective using either a
follower’s δ-approximate solution, or simply a follower’s feasible decision. Merging these two ideas, we show
that, for any ε > 0, a weak ε-local optimal solution can be found in a polynomial number of improving steps
in terms of the leader’s objective function’s parameters and 1/ε. Furthermore, if the follower’s problem
admits a δ-approximation algorithm, then the proposed approach is guaranteed to return an O(ε + δ)-local
optimal solution for the leader. Our computational experiments demonstrate that the proposed approach
significantly reduces the runtime compared to standard local search, while maintaining a solution of
comparable quality. This is a joint work with Eneko Clemente.
Bio
Oleg A. Prokopyev is a professor of Quantitative Business Administration at the University of Zurich
since February 2023. Prior to that, he was a professor at the University of Pittsburgh. He received his Ph.D.
from the University of Florida. His research interests are in the broad area of operations research with a
focus on combinatorial, bilevel and online optimization as well as their applications. Prof. Prokopyev is
the Co-Editor-in-Chief of Optimization Letters and serves on the editorial boards of IISE Transactions and
Journal of Global Optimization.