Despite the success of branch-and-cut methods for solving mixed integer bilevel linear optimization problems (MIBLPs) in practice, there have remained some gaps in the theory surrounding these methods. In this paper, we take a first step towards laying out a theory of valid inequalities and cutting-plane methods for MIBLPs that parallels the existing theory for mixed integer linear optimization problems (MILPs). We provide a general scheme for classifying valid inequalities and illustrate how the known classes of valid inequalities fit into this categorization. We also introduce new classes of valid inequalities—one based on a generalization of Chvatal inequalities for MILPs and several more based on a notion of parametric inequality similar to subadditive inequalities for MILPs. Finally, we compare the performance of all classes discussed in the paper using the open source solver MibS.
Citation
Laboratory for Computational Optimization Research at Lehigh (COR@L) Technical Report 20T-013.