Network Flow-Based Cuts for Binary Bilevel Optimization

Speaker: Sebastian Vasquez Abstract: Solving binary bilevel programs remains challenging due to the lack of strong, tractable single-level relaxations. Recent work embeds network representations of the follower’s value function into the high-point relaxation, yielding exact extended reformulations and valid bounds, but scalability is often limited by network size. We propose a network flow-based framework that instead uses these networks as oracles to derive cuts directly in the original variable space. Building on existing approaches, we introduce new exact reformulations and strengthen cut families by exploiting the network structure. Computational results show that the resulting cut-based method recovers the extended reformulation bound faster while integrating more naturally with state-of-the-art solvers. Bio: I earned a BS in Industrial Engineering and an MS in Operations Research from Pontificia Universidad Católica de Chile (PUC Chile). I then worked for two years as a software engineer at a Chilean consulting company, developing routing heuristics. I am currently pursuing a PhD in Operations Research at Carnegie Mellon University (CMU), where I work with Willem-Jan van Hoeve on discrete bilevel optimization.