In this paper, we study bilevel mixed integer programming (MIP) problem and present a novel computing scheme based on reformulations and decomposition strategy. By converting bilevel MIP into a constrained mathematical program, we present its single-level reformulations that are friendly to perform analysis and build insights. Then, we develop a decomposition algorithm based on column-and-constraint generation method, which converges to the optimal value within nite operations. A preliminary computational study on randomly generated instances is presented, which demonstrates that the developed computing scheme has a superior capacity over existing methods. As it is generally applicable, easy-to-use and computationally strong, we believe that this solution method makes an important progress in solving challenging bilevel MIP problem.
Article
View Solving Bilevel Mixed Integer Program by Reformulations and Decomposition