Title: A Projection-Based Reformulation and Decomposition Algorithm for Global Optimization of a Class of Mixed Integer Bilevel Linear Programs,
Abstract: We propose an extended variant of the reformulation and decomposition
algorithm for solving a special class of mixed-integer bilevel linear programs
(MIBLPs) where continuous and integer variables are involved in both upper- and
lower-level problems. In particular, we consider MIBLPs with upper-level
constraints that involve lower-level variables. We assume that the inducible
region is nonempty and all variables are bounded. By using the reformulation
and decomposition scheme, an MIBLP is first converted into its equivalent
single-level formulation, then computed by a column-and-constraint generation
based decomposition algorithm. The solution procedure is enhanced by a
projection strategy that does not require the relatively complete response
property. To ensure its performance, we prove that our new method converges to
the global optimal solution in a finite number of iterations. A large-scale
computational study on random instances and instances of hierarchical supply
chain planning are presented to demonstrate the effectiveness of the algorithm.