Rational arithmetic for Gomory’s fractional method

This paper intends to investigate the inherent behavior of Gomory’s fractional method for pure integer linear programming problems without cancellation of significant digits and round off errors in floating-point arithmetic. A rational arithmetic code which treats big integers is developed for this purpose. The computational results of twenty-six well known test problems solved by the developed rational arithmetic code and some floating-point arithmetic codes are compared and discussed. Some inherent characteristics of the fractional method are clarified: even if the rational arithmetic code is used, there may be some cases where the fractional method requires a large number of cuts to converge and it may tend to get stuck at some value of the objective function. The effect of cut generation and cut removal rules to the efficiency of the fractional method is also discussed. [In Japanese.]