Solving Mixed-Integer Nonlinear Programs by QP-Diving
Solving Mixed-Integer Nonlinear Programs by QP-Diving
复制标题
通过 QP-Diving 求解混合整数非线性规划
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
C. Kirches
中科院分区：
文献类型：
--
作者：
Ashutosh Mahajan;S. Leyffer;C. Kirches
提出了一种求解混合整数非线性规划问题的树搜索算法。而不是依赖于计算昂贵的非线性解决在每个节点的分支绑定树，我们的算法解决了一个二次近似在每个节点。我们表明，所得到的算法保持全局收敛性凸MINLP，我们提出了一系列的测试问题的数值结果。我们的数值经验表明，新的算法允许我们利用二次规划的热启动技术，从而减少求解时间凸MINLP的数量级上的某些类的问题。
We present a new tree-search algorithm for solving mixed-integer nonlinear programs (MINLPs). Rather than relying on computationally expensive nonlinear solves at every node of the branchand-bound tree, our algorithm solves a quadratic approximation at every node. We show that the resulting algorithm retains global convergence properties for convex MINLPs, and we present numerical results on a range of test problems. Our numerical experience shows that the new algorithm allows us to exploit warm-starting techniques from quadratic programming, resulting in a reduction in solve times for convex MINLPs by orders of magnitude on some classes of problems.