Bilevel Optimization with Discrete Submodular Lower Levels

Bilevel optimization (BLO) models hierarchical decision-making in applications such as electronic design automation, network planning, and learning systems. While recent advances in continuous settings have substantially expanded the scale and scope of solvable problems, many practical discrete BLO problems remain computationally difficult. This work studies BLO problems with discrete submodular lower levels (LLs) and coupled constraints, and introduces BiGAP, a randomized-smoothed value-function formulation that regularizes discrete response switches while preserving exact discrete oracles. We establish finite penalty exactness and show that the smoothed formulation agrees locally with the smoothed optimistic objective on positive-gap neighborhoods. The resulting first-order algorithms reduce all discrete computations to tractable unconstrained submodular function minimization (SFM), with $O({ϵ}^{-4})$ SFM complexity without coupled constraints and $O({ϵ}^{-6})$ with coupled constraints under exact dual support and uniform saddle-system conditioning. Experiments on challenging large-scale discrete optimization problems demonstrate the effectiveness and scalability of the proposed approach.