Theoretical and Numerical Comparison of Nine Single-Level Reformulations for Bilevel Programs

This paper considers a bilevel program. To solve this bilevel program, it is generally necessary to transform it into some single-level optimization problem. One approach is to replace the lower-level program by its KKT conditions to transform the bilevel program as a mathematical program with complementarity constraints (MPCC). Another approach is to apply the lower-level Wolfe/Mond-Weir/extended Mond-Weir duality to transform the bilevel program into some duality-based single-level reformulations, called WDP, MDP, and eMDP, respectively, in the literature. In this paper, inspired by a conjecture from a recent publication that the tighter feasible region of a reformulation, the better its numerical performance, we present five new duality-based single-level reformulations, called TWDP/TMDP/eTMDP/ETMDP/eETMDP, with tighter feasible regions. Our main goal is to compare all above-mentioned reformulations by designing some direct and relaxation algorithms with projection and implementing these algorithms on 450 test examples generated randomly. Our numerical experiments show that, whether overall comparison or pairwise comparison, at least in our tests, in terms of dominant cases and objective values, WDP/MDP/TWDP/TMDP/ETMDP were always better than MPCC, whereas eMDP/eTMDP/eETMDP were always the worst ones among eight duality-based reformulations, which indicates that the above conjecture is incorrect. In particular, for the relaxation algorithms, WDP/MDP/TWDP/TMDP performed four to five times better than MPCC, whereas eMDP/eTMDP/ETMDP/eETMDP performed at least 1.8 times better than MPCC in terms of dominant cases.

History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis.

Funding: This research was supported by the National Natural Science Foundation of China [Grants 12571324, 72501169, and 72394365], the China Postdoctoral Science Foundation [Grant 2024M761920], and the Postdoctoral Fellowship Program of the China Postdoctoral Science Foundation [Grant GZC20250524].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1159) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1159). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.