The multi-dimensional multiple-choice knapsack problem is an integer programming problem with n zero–one variables, r resource constraints, and m mutually disjoint multiple-choice constraints. The importance of the problem stems from the ease with which the appropriate specification of its parameters allows for the formulation of several important integer programming problems having widespread application. The concept of dominance allows the identification of variables which can be deleted from the problem prior to the enumeration phase. The expected proportion of undominated variables in multi-dimensional multiple-choice knapsack problems is shown to be a function of r, the number of resource constraints, and c, the cardinality of the multiple-choice sets. Explicit closed form solutions are given for r = 1, 2, and an approximation, for fixed r and large c. For general r and c, a recursive formula is given and results tabulated for a region of interest. For small values of r the proportion of undominated variables is small. The results provide theoretical support for the effectiveness of dominance testing in ‘pre-enumeration reduction’ procedures. The results also provide assistance to analysts in determining whether to use dominance testing in such procedures.
