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

• 成果类型: Article
• 署名作者: Gaar, Elisabeth; Lee, Jon; Ljubic, Ivana; Sinnl, Markus; Taninmis, Kuebra
• 署名单位: Johannes Kepler University Linz; Johannes Kepler University Linz; University of Michigan System; University of Michigan; ESSEC Business School
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01965-1
• 发表日期: 2024
• 页码: 91-124
• 关键词: branch-and-sandwich; global optimization algorithm; inequalities

摘要

We study a class of integer bilevel programs with second-order cone constraints at the upper-level and a convex-quadratic objective function and linear constraints at the lower-level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a second-order-cone-based cut-generating procedure. We propose DC separation strategies and consider several approaches for removing redundant disjunctions and normalization. Using these DCs, we propose 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 an extensive computational study on a diverse set of instances, including instances with binary and with integer variables, and instances with a single and with multiple linking constraints. Our computational study demonstrates that the proposed enhancements of our solution approaches are effective for improving the performance. Moreover, both of 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 binary instances.