高效求解整数线性规划问题的分支算法

Effective branch algorithm for integer linear programming problems

为了提高求解一般整数线性规划问题的效率,提出了一种基于目标函数超平面移动的分支算法。对于给定的目标函数整数值,首先利用线性规划松弛问题的最优单纯形表确定变量的上、下界,然后将变量的上、下界条件加入约束条件中对相应的目标函数超平面进行切割,最后应用分支定界算法中的分支方法来搜寻目标函数超平面上的可行解。通过对一些经典的数值例子的求解计算并与经典的分支定界算法进行比较,结果表明,该算法减少了分支数和单纯形迭代数,具有较大的实用价值。

In order to improve the computational efficiency,a branch algorithm for general integer linear programming problems on the objective function hyperplane shifts was presented.First,for a given integer value of the objective function,the lower and upper bounds of the variables were determined by the optimum simplex tableau of the linear programming relaxation problem.Then the conditions on the bounds were added to the constraints as cuts to the associated objective function hyperplane.Finally,a branch procedure of the branch-and-bound algorithm was applied to finding a feasible solution on the objective function hyperplane.The computational test on some classical numerical examples shows that,compared with the classical branch-and-bound principle,the algorithm greatly decreases the number of branches and the number of iterations in computation,and therefore,is of practical value.