SOCP-based disjunctive cuts for a class of integer nonlinear bilevel programs

We study a class of bilevel integer programs with second-order cone constraints at the upper level and a convex quadratic objective and linear constraints at the lower level. We develop disjunctive cuts to separate bilevel infeasible points using a second-order-cone-based cut-generating procedure. T...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-03
Main Authors: Gaar, Elisabeth, Lee, Jon, Ljubić, Ivana, Sinnl, Markus, Tanınmış, Kübra
Format: Article
Language:English
Subjects:
Algorithms
Job shops
Linearization
Mixed integer
Optimization
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study a class of bilevel integer programs with second-order cone constraints at the upper level and a convex quadratic objective and linear constraints at the lower level. We develop disjunctive cuts to separate bilevel infeasible points using a second-order-cone-based cut-generating procedure. To the best of our knowledge, this is the first time disjunctive cuts are studied in the context of discrete bilevel optimization. Using these disjunctive cuts, we establish a branch-and-cut algorithm for the problem class we study, and a cutting plane method for the problem variant with only binary variables. We present a preliminary computational study on instances with no second-order cone constraints at the upper level and a single linear constraint at the lower level. Our study demonstrates that both our approaches outperform a state-of-the-art generic solver for mixed-integer bilevel linear programs that is able to solve a linearized version of our test instances, where the non-linearities are linearized in a McCormick fashion.
ISSN:2331-8422
DOI:10.48550/arxiv.2111.06824