Using Disjunctive Cuts in a Branch-and-Cut Method to Solve Convex Integer Nonlinear Bilevel Problems

We present a branch-and-cut method for solving convex integer nonlinear bilevel problems, i.e., bilevel models with nonlinear but convex objective functions and constraints in both the upper and the lower level. To this end, we generalize the idea of using disjunctive cuts to cut off integer-feasible but bilevel-infeasible points. These cuts can be obtained by solving a cut-generating problem, which itself is a single-level but nonconvex integer nonlinear problem. We show that this cut-generating problem can be decomposed into a series of smaller subproblems. These can all be solved in parallel and we state sufficient conditions to ensure that they are convex integer nonlinear problems. Moreover, we develop additional algorithmic techniques such as tailored pruning rules to further speed up our method. We finally prove the correctness of the method and test it in a numerical study that shows the applicability of the method.

Article

Download

View PDF