Assessing Triviality in Random Mixed-Integer Bilevel Optimization Problems to Improve Problem Generators and Libraries

While bilevel optimization is gaining prominence across various domains, the field lacks standardized tools for generating test problems that can effectively evaluate and guide the development of efficient solution algorithms. We define the term "trivial bilevel optimization problem" as a bilevel problem whose high-point relaxation solution is also feasible. These easy-to-solve problems frequently arise in na�ve implementations of random bilevel optimization problem generators, significantly impacting the evaluation of bilevel solution algorithms. However, this problem has not been addressed in the literature to our best knowledge. This work introduces a non-trivial mixed-integer bilevel optimization problem generator, NT-BMIPGen, and a problem library, designed to eliminate the generation of trivial bilevel problems. Through analysis of the bilevel problem structure, we identify key factors contributing to problem triviality. Particularly, the upper to lower variable ratios and the number of decoupled lower-level continuous variables increasing two-level competition significantly impact problem triviality. The proposed generator allows users to customize problem structures while ensuring non-triviality by checking the bilevel feasibility of highpoint relaxation. Additionally, we present a library of 105 non-trivial problems to support algorithm development and testing. This work advances the understanding of bilevel problem complexity and provides essential tools for the systematic evaluation of bilevel optimization algorithms.