Integer bilevel problems solved with new cutting plane method
On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts
Discrete Mathematics
Summary
Bilevel optimization problems are challenging because one decision depends on another decision made later. This paper looks at cases where all decisions must be whole numbers, the first decision maker uses simple rules, but the second decision maker’s goal is more complex. The authors develop a new way to rule out bad solutions using a special kind of cut called disjunctive cuts, which are found by solving simpler problems within the main problem. They then test their approach and find it works better than existing methods on several example problems.
What this means in practice
- •For operations research teams: Solve complex hierarchical integer optimization problems where the lower-level decision has a quadratic, possibly non-convex, objective.
- •For supply chain planners: Improve decision-making for planning problems with two-level integer decisions and complex follower goals using efficient cut-based algorithms.
Authors
Kübra Tanınmış, Elisabeth Gaar, Jon Lee, Ivana Ljubić, Markus Sinnl
Abstract
In this work, we study bilevel optimization problems where all variables are integer, all constraints and the leader objective function are linear, and the follower objective function is non-convex quadratic. Relying on bilevel-free sets derived from improving directions, we develop a disjunctive cut approach to exclude bilevel-infeasible solutions within a branch-and-cut algorithm. We show that our disjunctive cuts can be obtained by solving a cut generating linear program. Furthermore, we discuss conditions that allow the number of disjuncts in the cut generating linear program to be reduced, and we propose several strategies to identify improving directions and generate disjunctive cuts efficiently. We evaluate various aspects of the proposed branch-and-cut algorithm on both convex instances from the literature that fit our setting and new non-convex instances and compare the performance of our best approach with existing state-of-the-art approaches, which we significantly outperform.