Branch-and-price for a class of nonconvex mixed-integer nonlinear programs
Branch-and-price for a class of nonconvex mixed-integer nonlinear programs
复制标题
一类非凸混合整数非线性规划的分支与价格
DOI：
--
复制
发表时间：
2020
影响因子：
1.8
通讯作者：
Qi Zhang
中科院分区：
文献类型：
--
作者：
A. Allman;Qi Zhang
这项工作试图结合在过去三十年中已经成熟的两种主要技术的优势：全局混合整数非线性优化和分支和价格。考虑一类具有线性复杂约束和整数连接变量的一般非凸混合整数非线性规划（minlp）。如果去除复杂的约束，问题就变得容易解决，例如，由于结构可分解。链接变量的完整性允许我们应用离散化方法推导dantzigg - wolfe重新表述，并使用分支和价格将问题求解为全局最优性。这是一个非常简单的想法；但令我们惊讶的是，它几乎没有在文献中找到任何应用。在这项工作中，我们表明许多相关问题直接属于或可以重新表述为这类minlp。我们提出了分支价格算法，并在考虑多个实际相关的大规模问题的广泛计算研究中证明了它的有效性（有时是无效的），表明在许多情况下，可以实现解决时间的数量级减少。
This work attempts to combine the strengths of two major technologies that have matured over the last three decades: global mixed-integer nonlinear optimization and branch-and-price. We consider a class of generally nonconvex mixed-integer nonlinear programs (MINLPs) with linear complicating constraints and integer linking variables. If the complicating constraints are removed, the problem becomes easy to solve, e.g. due to decomposable structure. Integrality of the linking variables allows us to apply a discretization approach to derive a Dantzig-Wolfe reformulation and solve the problem to global optimality using branch-andprice. It is a remarkably simple idea; but to our surprise, it has barely found any application in the literature. In this work, we show that many relevant problems directly fall or can be reformulated into this class of MINLPs. We present the branch-and-price algorithm and demonstrate its effectiveness (and sometimes ineffectiveness) in an extensive computational study considering multiple large-scale problems of practical relevance, showing that, in many cases, orders-of-magnitude reductions in solution time can be achieved.