Comparison of Some Algorithms for Solving the Group Theoretic Integer Programming Problem

Gomory has shown that the group-theoretic problem associated with an integer programming problem can be treated as a shortest-route problem. Thus one may solve it by a standard shortest-route algorithm. However, because of the special properties of the constructed problem, one can simplify and modify the algorithm. This paper presents five such simplified algorithms and compares their computational results with the group-theoretic algorithms developed by Gomory, Hu, and Shapiro.