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.