A Method for Solving Discrete Optimization Problems

This paper describes a simple, easily-programmed method for solving discrete optimization problems with monotone objective functions and completely arbitrary (possibly nonconvex) constraints. The method is essentially one of partial enumeration, and is closely related to the “lexicographic” algorithm of Gilmore and Gomory for the “knapsack” problem and to the “additive” algorithm of Balas for the general integer linear programming problem. The results of a number of sample computations are reported. These indicate that the method is computationally feasible for problems in which the number of variables is fairly small.