分支-切割法的框架及收敛性

Framework and convergence of branch-and-cut algorithms

在解决各类整数规划问题时,分支-切割法是一个非常成功的方法,并且它能保证给出一个最优解。从一个简单例子出发引出分支-切割算法的思想,从而给出其算法框架,并对其收敛性进行分析。

Branch-and-cut methods are very successful techniques for solving a wide variety of integer programming problems,and they can provide a guarantee optimality. In this paper, we derive the thought of branch-and-cut algorithms from a simple example, giving the framework of the algorithms and analyzing if the algorithms converge or not.