Network flow-based cuts for binary bilevel programs
Abstract
Binary bilevel programs are challenging to solve due to the lack of compact single-level reformulations. Recent extended network flow-based reformulations have emerged as a promising approach, providing strong dual bounds. However, their increasing size can make them computationally prohibitive. We develop a cutting-plane framework that exploits these networks without requiring an extended-space formulation. We introduce two exact network flow-based reformulations and provide an efficient separation procedure for inequalities that certify the follower's optimality. We further strengthen these inequalities through a tilting procedure that leverages the combinatorial structure of the networks. Computational experiments show that the proposed approach becomes increasingly advantageous as networks grow larger or more numerous. Moreover, incorporating the cuts into state-of-the-art bilevel solvers improves solution times and optimality gaps on BOBILib instances, closing eight more open instances than the baseline solvers. These results demonstrate the effectiveness of using network representations as separation oracles for binary bilevel optimization.
Related
- On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts
- A novel L-shaped refinement chain cuts method for two-stage stochastic programs
- On the Tightness of Standard Relaxations for Mixed-Integer Bilevel Linear Programs
- A Theoretical Analysis of a Bilevel Optimization Formulation for Combined Local-Global Optical Flow Models
- A Bilevel Market Equilibrium Model for Natural Gas Pipeline Network Operations: Convex Relaxations and Single-level Reformulations
BibTeX
@misc{vasquez2026network,
title = {{Network flow-based cuts for binary bilevel programs}},
author = {Sebastian Vasquez and Leonardo Lozano and Willem-Jan van Hoeve},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39261},
eprint = {2610.39261},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39261},
}
RIS
TY - UNPB
TI - Network flow-based cuts for binary bilevel programs
AU - Sebastian Vasquez
AU - Leonardo Lozano
AU - Willem-Jan van Hoeve
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39261
UR - https://arxiv.org/abs/2610.39261
AB - Binary bilevel programs are challenging to solve due to the lack of compact single-level reformulations. Recent extended network flow-based reformulations have emerged as a promising approach, providing strong dual bounds. However, their increasing size can make them computationally prohibitive. We develop a cutting-plane framework that exploits these networks without requiring an extended-space formulation. We introduce two exact network flow-based reformulations and provide an efficient separation procedure for inequalities that certify the follower's optimality. We further strengthen these inequalities through a tilting procedure that leverages the combinatorial structure of the networks. Computational experiments show that the proposed approach becomes increasingly advantageous as networks grow larger or more numerous. Moreover, incorporating the cuts into state-of-the-art bilevel solvers improves solution times and optimality gaps on BOBILib instances, closing eight more open instances than the baseline solvers. These results demonstrate the effectiveness of using network representations as separation oracles for binary bilevel optimization.
ER -