Network Relaxations for Combinatorial Bilevel Optimization Under Linear Interactions

Abstract

A Network View of Bilevel Optimization Many decision problems are inherently hierarchical; a leader acts first while anticipating that a follower will respond optimally. Determining the leader’s best decision is notoriously difficult in areas such as infrastructure design, transportation, and security, especially when decisions are discrete. In “Network Relaxations for Combinatorial Bilevel Optimization under Linear Interactions,” Leonardo Lozano, David Bergman, and Andre Cire introduce a new representation for problems in which leader-follower interactions are captured by linear inequalities involving binary leader decisions. Their approach uses a layered decision-diagram network whose paths encode the leader’s choices and whose terminal values represent the follower’s optimal objective value. The network reveals symmetries, supports strong flow-based formulations, and can be compressed through node aggregation to create tractable approximations. Computational tests on previously unresolved benchmark problems show substantial improvements over leading bilevel solvers, proving optimality for many open instances and pointing to promising directions for future research in the field.