论文标题
在基于SOCP的脱节削减上，以求解一类整数二线非线性程序
On SOCP-based disjunctive cuts for solving a class of integer bilevel nonlinear programs
论文作者
论文摘要
我们研究一类Integer Bilevel程序，具有二阶圆锥限制在上层的二阶限制，以及下层的凸 - 二次目标函数和线性约束。我们开发了析出剪切（DC），以使用二阶基于二阶的切割生成程序来分离双杆状的解决方案。我们提出了直流分离策略，并考虑了消除冗余析取和归一化的几种方法。使用这些DC，我们为我们研究的问题类提出了一种分支和切割算法，以及仅使用二进制变量的问题变体的切削平面方法。 我们对各种实例进行了广泛的计算研究，包括具有二进制和整数变量的实例，以及具有多个链接约束的实例。我们的计算研究表明，提出的解决方案方法的提高对提高性能有效。此外，我们的两种方法都超过了混合组合双线性线性程序的最先进的通用求解器，该程序能够求解我们二进制实例的线性化版本。
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.
