Jointly with Martin Schmidt

Year: 2025

Abstract: Bilevel optimization problems arise in numerous real-world applications. While single-level reformulations are a common strategy for solving convex bilevel problems, such approaches usually fail when the follower's problem includes integer variables. In this paper, we present the first single-level reformulation for mixed-integer linear bilevel optimization, which does not rely on the follower's value function. Our approach is based on convexifying the follower's problem via a Dantzig-Wolfe reformulation and exploits strong duality of the reformulated problem. By doing so, we derive a nonlinear single-level problem, which is equivalent to the original bilevel model. Moreover, we show that this problem can be transformed into a mixed-integer linear problem using standard linearization techniques and bounds on the dual variables of the convexified follower's problem. Notably, we show that these bounds can be computed in practice via a polynomial-time-solvable problem, which is purely based on the primal problem's data. This results in a new branch-and-cut approach for mixed-integer linear bilevel optimization. In addition to this exact solution approach, we also present a penalty alternating direction method, which computes high-quality feasible points. Numerical experiments on instances from the BOBILib shows that we are able to improve the best known solution of 427 instances out of a test set of 2216 instances.

Cite as:

@techreport{lefebvre2025reformulation,
  title={A New Single-Level Reformulation for Mixed-Integer Bilevel Optimization: Exact and Heuristic Approaches},
  author={Henri Lefebvre and Martin Schmidt},
  year={2025},
  archivePrefix={Optimization Online},
  url={https://optimization-online.org/?p=30703}
}

Open Access

Optimization Online

Open Data

All the instances which were used can be found on the BOBILib website. As described in the paper, we considered all instances from the collection (visited on the 05/06/2025) which have binary leader decisions and bounded high-point relaxation.

Open Methodology

Our data transformations can be found here.

Open Source

An implementation of the PADM is available in the open-source C++ library idol.

Open Educational Resources

A poster which were presented at the MIP Europ Workshop is available here.