<p>Binary bilevel programs are notoriously difficult to solve due to the absence of strong and efficiently computable relaxations. In this work, we introduce a novel single-level reformulation of these programs by leveraging a network flow-based representation of the follower’s value function, utilizing decision diagrams and linear programming duality. This approach enables the development of scalable relaxations by applying it to a restricted solution set, which in turn provides dual bounds. We obtain an exact method by iteratively solving and strengthening the relaxation. We further extend the reformulation to address the pessimistic version of the original bilevel problem. We experimentally compare our method with state-of-the-art bilevel programming solvers, demonstrating competitive performance. Specifically, on the BOBILib benchmark set our approach provides new or improved bounds for six instances and closes two open instances for the first time. We also show experimentally that the decision diagram reformulation can be particularly effective when it can leverage the combinatorial structure of the follower’s problem.</p>