The role of Improving Directions in Mixed Integer Bilevel Linear Optimization

Speaker: Federico Battista Abstract: We study the central role of improving directions in solution methods for mixed-integer bilevel linear optimization problems (MIBLPs). State-of-the-art methods adapt the branch-and-cut framework originally developed for single-level optimization. These methods rely on two types of oracles: those that determine whether a candidate pair of leader's and follower's decisions is bilevel feasible, and those that generate valid inequalities. Although these oracles are typically managed separately, we reveal a close connection between them and propose a solution framework centered on a single type of subproblem: determining whether an improving feasible direction exists for the follower’s problem. Solving this subproblem provides information that can be used both to check bilevel feasibility and to generate strong valid inequalities. Building on previous work, we clarify the foundational role of improving directions in enforcing the follower’s optimality condition. We also extend a known hierarchy of optimality-based relaxations to the mixed-integer setting and connect the resulting feasible regions to valid inequalities derived from improving directions. These insights lead to practical computational improvements, which we demonstrate using a modified version of the open-source solver MibS. Bio: Federico Battista is a Postdoctoral Researcher in the Dept. of Industrial and Systems Engineering at the University of Southern California. He received his PhD in Operations Research from Sapienza University of Rome in 2023, after a M.Sc. in Computer Science at University of L'Aquila. Before joining USC, he was a Postdoctoral Researcher at Lehigh University where he contributed to the development of MibS, the open-source COIN-OR solver for bilevel optimization. His research lies at the intersection of theory, algorithms, and computation in discrete optimization with a focus on branch-and-cut methods for mixed-integer linear, bilevel, and combinatorial optimization problems.