整数线性规划的切割与分支算法

Cut and branch algorithm of general integer linear programming problems

基于整数线性规划问题的分支定界方法,以子问题或根问题的目标最优值作为参数,构造了一种新的切割不等式,能够方便地切割子问题或根问题的非整数最优解。在分支之前进行这种切割,产生了一种新的求解整数线性规划问题的切割与分支算法。将该算法应用于求解一些经典的数值例子,实验结果表明,与经典的分支定界方法相比,该算法大大减少了分支的数量,提高了计算效率。随着问题规模的增大,该算法的计算优越性体现得更加明显。

On the basis of the classical branch-and-bound principle,a new cutting inequality with the optimum value of a child or root problem as a parameter is constructed.So,the optimal non-integer solution of the child or root problem can be conveniently cut off by the associated cutting plane with the cutting inequality.Performing the cutting before the branching,a new cutting and branch algorithm for general integer linear programming problems is presented.The computational test on some classical numerical examples show that,compared with the classical branch-and-bound principle,the algorithm greatly decreases the number of the branches,improves the com-putational efficiency.With the increase of the problem size,the superiority of the algorithm is remarkable.