A Note on Degeneracy in Integer Linear Programming Problem

A set of three batches of 1000 randomly produced integer linear programming problems of different sizes was solved using a partial enumeration algorithm. That particular algorithm involves the initial ordering of the variables according to their attractiveness when considered individually. The results reveal that, as might have been expected, the most attractive variables appear very much more frequently than do the less attractive. Perhaps less expected is the fact that the average number of variables appearing in the optimum solution is considerably less than might have been anticipated. Thus, for example, the average number of variables which appear in a set of problems featuring 20 variables and 10 constraints is only 4.14, as against the 10 one would have been expecting in continuous LP problems of that size. It is argued that it is this inherent characteristic which results in truncation solution procedures being as effective as they are.