Solving linear programs with complementarity constraints using branch-and-cut
Solving linear programs with complementarity constraints using branch-and-cut
复制标题
使用分支剪切法求解具有互补约束的线性规划
DOI：
10.1007/s12532-018-0149-2
复制
发表时间：
2019
影响因子：
6.3
通讯作者：
Pang, Jong-Shi
中科院分区：
文献类型：
--
作者：
Yu, Bin;Mitchell, John E.;Pang, Jong-Shi
具有线性互补约束的线性规划(LPCC)要求在一组线性约束上最小化一个线性目标以及附加的线性互补约束。这个类已经成为一个广泛的问题集合的建模范例，包括双层规划、Stackelberg博弈、逆二次规划和涉及均衡约束的问题。互补约束的存在导致了一个非凸优化问题。我们开发了一种分支切割算法来寻找这类优化问题的全局最优解，其中我们直接对互补进行分支。我们开发了分支规则和可行性恢复程序，并通过与CPLEX的比较证明了它们的计算效率。该实现通过使用回调例程构建在CPLEX之上。计算结果表明，与用大M项表示变量的界相比，我们的方法是构造整数规划公式的一种强有力的选择，并在一般的LPC以及具有凸二次低层问题的双层规划的实例上进行了测试。
A linear program with linear complementarity constraints (LPCC) requires the minimization of a linear objective over a set of linear constraints together with additional linear complementarity constraints. This class has emerged as a modeling paradigm for a broad collection of problems, including bilevel programs, Stackelberg games, inverse quadratic programs, and problems involving equilibrium constraints. The presence of the complementarity constraints results in a nonconvex optimization problem. We develop a branch-and-cut algorithm to find a global optimum for this class of optimization problems, where we branch directly on complementarities. We develop branching rules and feasibility recovery procedures and demonstrate their computational effectiveness in a comparison with CPLEX. The implementation builds on CPLEX through the use of callback routines. The computational results show that our approach is a strong alternative to constructing an integer programming formulation using big-Mterms to represent bounds for variables, with testing conducted on general LPCCs as well as on instances generated from bilevel programs with convex quadratic lower level problems.
登录
查看更多内容
影响因子：
2.7
作者：
A. Fügenschuh;Alexander Martin
通讯作者：
Alexander Martin
用LPCC全局求解支持向量机回归参数选择问题
影响因子：
2.4
作者：
Yu;J. Pang;J. Mitchell
通讯作者：
J. Mitchell
影响因子：
6.3
作者：
Tobias Fischer;M. Pfetsch
通讯作者：
Tobias Fischer;M. Pfetsch
具有线性互补约束的线性规划的旋转算法
影响因子：
2.2
作者：
Haw;S. Leyffer;T. Munson
通讯作者：
T. Munson
DOI：
--
发表时间：
1978
期刊：
影响因子：
--
作者：
R. Jeroslow
通讯作者：
R. Jeroslow