NWO-DFG Exploiting Symmetries for Faster Bilevel Optimization Algorithms

• Applicant: Professor Dr. Martin Schmidt
• Subject Area: Mathematics
• Term: since 2026
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 567152707

Bilevel programming (BP) is a popular mathematical framework for modeling hierarchical decision-making processes involving two players, a leader and a follower. In counter-terrorism applications, e.g., leaders secure some infrastructure to minimize the effect of the follower's attacks. Other applications arise, e.g., in energy network design (END). To find optimal solutions to such BP problems, many techniques from the related field of mixed-integer programming (MIP) have been transferred to BP. Today's BP technology can only solve problems of rather small scale though, since these MIP techniques are considered independently. By combining different techniques, synergies can be created, which are urgently needed to solve real-world problems, e.g., in today's END. This, however, requires expert knowledge on the respective techniques, which is very demanding for a single researcher and a mono-disciplinary approach. The ambitious goal of this collaborative proposal is to combine, for the first time, symmetries and BP cutting planes. The PIs are leading experts in either field, creating a unique expertise that is necessary to realize this research. When successful, tremendous performance gains are realized that allow to solve more realistic BP problems, e.g., energy networks with hundreds of nodes rather than dozens. We therefore develop, for the first time, a novel mathematical theory of bilevel symmetries and effective algorithms for handling these symmetries. The MIP literature has used symmetries mainly to accelerate algorithms by discarding symmetric regions of the problem's solution space. Next to classic symmetry handling, our groundbreaking idea is to strengthen existing BP technology by taking symmetries into account. The latter achieves a much stronger coupling between the actions of the leader and the follower, which will result in more effective algorithms for solving BP problems. In this project, our international team (Eindhoven, Trier) realizes these innovative ideas by developing a unique theory of bilevel symmetries, generalizing symmetry handling algorithms from MIP to BP, and developing novel symmetry handling algorithms that are tailored for BP. All our theoretically developed techniques will also be implemented in state-of-the-art open-source BP software such that both researchers and practitioners from various fields, e.g., economics and engineering, can immediately benefit by solving their problems faster by using our software.

• DFG Programme: Research Grants
• International Connection: Netherlands
• Cooperation Partner: Professor Dr. Christopher Hojny