CONSTRUCTIVE GROUP RELAXATIONS FOR INTEGER PROGRAMS

Recent work by M. L. Fisher and J. F. Shapiro has used R. E. Gomory's group theoretic methods together with Lagrange multipliers to obtain bounds for the optimal value of integer programs. Here it is shown how an extension of the associated Abelian group can improve the bound without the artificiality of adding a cut. It is proved that there exists a finite group for which the dual ascent procedure of Fisher and Shapiro converges to the optimal integer solution. Constructive methods are given for finding this group. A worked example is included.