A single-level reformulation of binary bilevel programs using decision diagrams

• 成果类型: Article; Early Access
• 署名作者: Vasquez, Sebastian; Lozano, Leonardo; Van Hoeve, Willem-Jan
• 署名单位: Carnegie Mellon University; University System of Ohio; University of Cincinnati
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02294-1
• 发表日期: 2025-12-16
• 关键词: bilevel optimization; integer programming; decision diagrams; NETWORK DESIGN PROBLEM; algorithm; REPRESENTATION; branch; bounds

摘要

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.