We present a branch-and-cut algorithm for solving discrete bilevel linear programs where the upper-level variables are binary and the lowerlevel variables are either pure integer or pure binary. This algorithm performs local search to find improved bilevel-feasible solutions. We strengthen the relaxed node subproblems in the branch-and-cut search tree by generating cuts to eliminate all of the upper level integer feasible solutions explored during the local search step. Furthermore, to avoid repeatedly solving similar bilevel integer problems in the local search, we derive structural properties of the value functions of bilevel integer programs. Most notably, we generalize the integer complementary slackness theorem to bilevel integer programs. We also propose three efficient approaches for computing the bilevel programming value functions. Our computational results show that the proposed branch-and-cut approach enhanced with the implementation of value functions and local search can solve discrete bilevel programming instances with up to 200 variables and 150 constraints in a reasonable amount of time.
Osman Y. Ozaltin is an Assistant Professor in the Edward P. Fitts Department of Industrial and Systems Engineering, and a member of the Personalized Medicine Faculty Cluster at the North Carolina State University. He received his MS and PhD degrees in Industrial Engineering from the University of Pittsburgh. His bachelor’s is in Industrial Engineering from Bogazici University, Turkey. His research interests span theoretical, computational, and applied aspects of mathematical programming, focusing on optimization problems arising in public health, personalized medicine and healthcare delivery. His methods include integer programming, combinatorial optimization, stochastic programming, bilevel programming, and quadratic programming.