Three enhancements for optimization-based bound tightening
Three enhancements for optimization-based bound tightening
复制标题
基于优化的边界紧缩的三个增强功能
DOI：
10.1007/s10898-016-0450-4
复制
发表时间：
2016
影响因子：
1.8
通讯作者：
Stefan Weltge
中科院分区：
文献类型：
--
作者：
Ambros M. Gleixner;Timo Berthold;Benjamin Müller;Stefan Weltge
基于优化的边界紧缩 (OBBT) 是减少非凸混合整数非线性程序 (MINLP) 变量域的最有效方法之一。同时，它也是最昂贵的边界紧缩程序之一，因为它求解辅助线性程序 (LP)——变量数量高达两倍。本文的主要目标是讨论有效实现 OBBT 的算法技术。大多数最先进的 MINLP 求解器都应用 OBBT 的某些受限版本，并且人们似乎普遍认为，如果只有一个能够控制其计算成本，则 OBBT 是有益的。为此，我们引入了三种技术来提高 OBBT 的效率：减少已求解 LP 数量的过滤策略、利用单纯形热启动的排序启发式以及拉格朗日变量界限 (LVB) 的生成。树搜索期间 LVB 的传播是 OBBT 的快速近似，无需求解辅助 LP。我们在 MINLPLib2 上进行了大量的计算实验。我们的结果表明 OBBT 在困难实例上最有益，我们观察到平均加速率为 17-19%。最重要的是，使用 OBBT 可以解决更多实例。
Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17–19 % on average. Most importantly, more instances can be solved when using OBBT.