On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts
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.
Related
- Disjunctive Submodular Functions: Envelopes and Applications to Inventory and 0-1 Quadratic Optimization
- Are Single-Leader-Multi-Follower Problems Particular Cases of Bilevel Optimization?
- Representing the Non-dominated Set of Multi-objective Optimization Problems with Polyhedral Ordering Cones
- Stabilized SQP Method for Convex Piecewise Linear-Quadratic Composite Optimization Problems
- Global Optimization of Mixed-Integer Bound-Constrained Quadratic Fractional Problems
BibTeX
@misc{tanınmıs2026solving,
title = {{On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts}},
author = {Kübra Tanınmış and Elisabeth Gaar and Jon Lee and Ivana Ljubić and Markus Sinnl},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01197},
eprint = {2610.01197},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01197},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts
AU - Kübra Tanınmış
AU - Elisabeth Gaar
AU - Jon Lee
AU - Ivana Ljubić
AU - Markus Sinnl
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01197
UR - https://arxiv.org/abs/2610.01197
AB - 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.
ER -