Network Relaxations for Combinatorial Bilevel Optimization Under Linear Interactions

We address mixed-integer bilevel linear programs in which a binary leader interacts with a follower through linear linking constraints. Despite the prevalence of such models in interdiction, pricing, and network design applications, existing high-point relaxations are often weak, leading to poor bounds and limited scalability. We propose a network-based representation of the follower’s value function using a layered decision diagram whose paths correspond to binary leader decisions and whose lengths encode the follower’s responses. This structure yields an exact extended formulation of the bilevel problem, a convex-hull flow model over the value function graph, and a parameterized hierarchy of tractable high-point relaxations obtained through node aggregation. We further establish connections with tender-variable formulations and develop algorithmic procedures that make the approach computationally practical. Extensive experiments on open instances from the BOBILib benchmark with up to 500 leader variables show that, when integrated into a standard cutting-plane framework, our method solves 344 previously open instances to optimality, achieves new best-known solutions in 681 cases, and outperforms two state-of-the-art solvers in more than 800 pairwise comparisons. These results demonstrate the practical value of exploiting value function structure and network approximations to enhance the tractability of bilevel optimization.

Funding: This work was supported by the Air Force Office of Scientific Research [FA9550-22-1-0236] and the Natural Sciences and Engineering Research Council of Canada [RGPIN-2020-06054 and RGPIN-2026-07964].

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2025.2457.