2343. Solving Multi-Follower Mixed-Integer Bilevel Problems with Binary Linking Variables
Invited abstract in session MA-17: Combinatorial bilevel optimization 1, stream Combinatorial Optimization.
Monday, 8:30-10:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Vladimir Stadnichuk
|
| Lehrstuhl für Operations Managemnt, RWTH Aachen | |
| 2. | Arie Koster
|
| Lehrstuhl II für Mathematik, RWTH Aachen University |
Abstract
We study multi-follower bilevel optimization problems with binary linking variables, where the second level consists of multiple independent integer-constrained subproblems. To solve these efficiently, we propose a novel branch-and-cut decomposition method that begins by solving the first-level problem and iteratively generates second-level feasibility and optimality cuts. These cuts are derived by solving a modified version of the second-level problem. Unlike many existing methods, our approach does not rely on solving the high-point relaxation of the bilevel problem. Instead, we fully project out the second level, providing significant computational advantages, particularly when the second-level problem is large or has a weak LP relaxation. Additionally, our method can be fully automated within a MIP solver, making it accessible to users who do not wish to design problem-specific algorithms. Our computational results demonstrate that our approach efficiently solves instances with hundreds of subproblems within minutes, significantly outperforming Benders-like decomposition methods from the literature on challenging instances.
Keywords
- Combinatorial Optimization
- Branch and Cut
- Programming, Mixed-Integer
Status: accepted
Back to the list of papers