A New Rounding Algorithm for Integer Linear Programming

Abstract

An algorithm is given for optimizing a linear function subject to integer linear constraints by a rounding method which is an extension of Gomory's. The range of computation to obtain the optimal solution to the integer linear problem by this algorithm is less than that of Gomory's. In particular, this algorithm is very effective in the case where the value of the product of the pivots is much larger than the number of nonbasic variables.