论文标题
一类非convex混合企业非线性程序的分支机构和价格
Branch-and-Price for a Class of Nonconvex Mixed-Integer Nonlinear Programs
论文作者
论文摘要
这项工作试图结合过去三十年中成熟的两种主要技术的优势：全球混合成员非线性优化和分支机构和价格。我们考虑使用线性复杂约束和整数链接变量的一类通常的非convex混合企业非线性程序（MINLP）。如果删除了复杂的约束，则问题很容易解决，例如由于可分解的结构。链接变量的完整性使我们能够采用离散化方法来得出Dantzig-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-and-price. 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.
