Extensions of the Group Theoretic Approach in Integer Programming

By relaxing the nonnegativity constraints on a set of basic variables, an integer programming problem can be reduced to a shortest route problem over a finite Abelian group. Here it is shown how given a similar relaxation on any set of variables, a structurally simpler problem is obtained, which can be regarded as a shortest route problem over an Abelian (but not necessarily finite) group. In particular if the non-negativity constraints are relaxed on all but one of a set of basic variables, a knapsack (or very close to knapsack) problem is obtained, which either gives the solution of the integer problem, or when solved by dynamic programming provides bounds at least as strong as those provided by the above group problem. The difficulty that arises when the order of groups encountered is very large is also considered in the same framework, and by further relaxation it is shown how the groups can be reduced to manageable size, which can be used to provide simple bounds for the above group problem. Finally applications of these results are suggested with reference to various existing integer programming algorithms.