An enhanced logical benders approach for linear programs with complementarity constraints
An enhanced logical benders approach for linear programs with complementarity constraints
复制标题
具有互补约束的线性程序的增强逻辑弯曲方法
DOI：
10.1007/s10898-020-00905-z
复制
发表时间：
2020
影响因子：
1.8
通讯作者：
Wächter, Andreas
中科院分区：
文献类型：
--
作者：
Jara-Moroni, Francisco;Mitchell, John E.;Pang, Jong-Shi;Wächter, Andreas
这项工作扩展了Hu等人（SIAM J Optim 19（1）：445-471，2008）和Bai等人（Comput Optim Appl 54（3）：517-554，2013）提出的用于求解具有互补约束的线性规划的逻辑benders方法。我们开发了一种新的解释的逻辑Benders方法作为一个反向分支定界搜索，整个探索过程开始从叶节点的枚举树。这种洞察力使我们能够提供一个新的框架，我们可以在一个单一的过程中结合联合收割机的主问题和削减一代。它还使我们能够使搜索多样化，在计算上导致更强的削减。我们还提出了一个基于优化的稀疏化过程，使切割生成更有效。数值结果表明了该方法的有效性。结果也扩展到更多的互补性约束的问题，超过那些可以处理的原始方法中引用的参考文献。
This work extends the logical benders approach for solving linear programs with complementarity constraints proposed by Hu et al. (SIAM J Optim 19(1):445–471, 2008) and Bai et al. (Comput Optim Appl 54(3):517–554, 2013). We develop a novel interpretation of the logical Benders method as a reversed branch-and-bound search, where the whole exploration procedure starts from the leaf nodes in an enumeration tree. This insight enables us to provide a new framework over which we can combine master problem and cut generation in a single process. It also allows us to diversify the search, leading computationally to stronger cuts. We also present an optimization-based sparsification process which makes the cut generation more efficient. Numerical results are presented to show the effectiveness of this enhanced method. Results are also extended to problems with more complementarity constraints, exceeding those that can be handled by the original method in the cited references.
登录
查看更多内容
影响因子：
6.3
作者：
Tobias Fischer;M. Pfetsch
通讯作者：
Tobias Fischer;M. Pfetsch
二元线性混合整数问题的基于信息的分支方案
影响因子：
6.3
作者：
F. Kılınç;G. Nemhauser;M. Savelsbergh
通讯作者：
M. Savelsbergh
DOI：
--
发表时间：
1978
期刊：
影响因子：
--
作者：
R. Jeroslow
通讯作者：
R. Jeroslow
技术说明 - 补充编程
影响因子：
2.7
作者：
T. Ibaraki
通讯作者：
T. Ibaraki
影响因子：
3.1
作者：
Burdakov, Oleg P.;Kanzow, Christian;Schwartz, Alexandra
通讯作者：
Schwartz, Alexandra