In order to solve large Multidimensional Knapsack problems we examine a technique which decomposes a problem instance into two parts. The first part is solved using a traditional technique, such as Dynamic Programming, to reduce the number of variables in the problem by creating a single variable with many non-dominated states. In the second part the remaining variables are determined by an algorithm that repeatedly enumerates them with different constraint and objective requirements. The constraint and objective requirements are imposed by the various non-dominated states of the variable created in the first part of this technique. The main advantage of this approach is that when memory requirements prevent traditional techniques solving a problem instance, the enumeration provides a much less memory-intensive method, enabling a solution to be found. Two approaches are proposed for repeatedly enumerating a 0/1 Multidimensional Knapsack problem. It is demonstrated how these enumeration methods, in conjunction with the Modular Approach, were used to find the optimal solutions to a number of 500-variable, 5-constraint Multidimensional Knapsack problem instances proposed in the literature. The exact solutions to these instances were previously unknown.

This paper develops an algorithm based on the Modular Approach to solve singly constrained separable discrete optimization problems (Nonlinear Knapsack Problems). The Modular Approach uses fathoming and integration techniques repeatedly. The fathoming reduces the decision space of variables. The integration reduces the number of variables in the problem by combining several variables into one variable. Computational experiments for "hard" test problems with up to 1000 variables are provided. Each variable has up to 1000 integer values.