Using Discrete Programming

In many important economic problems, a variable is maximized subject to constraints. In a subset of such problems, a linear combination of decision variables is maximized subject to linear constraints. The latter subset is amenable to linear programming analysis. Efforts to expand the usefulness of linear programming methods usually involve incorporating nonlinear elements either in the criterion function or in the constraints. Such efforts frequently result in discovering ways to incorporate the nonlinear element in some acceptable linear form, thus retaining the usual linear programming procedure but broadening the researcher's capacity to apply the method to important economic problems (9).1 Discrete programming is a case in point. Discrete programming problems and ordinary linear programming problems are about the same, except that a side condition is imposed that some of the decision variables must take on discrete values, usually nonnegative integers. The resultant, noncontinuous nature of the criterion function or of the constraints places discrete programming in the class of nonlinear programming (10). Sufficient conditions for a solution to discrete programming problems have been known for several years (15). Recently, systematic procedures for solving discrete programming problems have been put forward (14, 16). This paper discusses one of them. Decks and tapes for solving such problems on high-speed computers are not yet abundant, but it would be easy to supply them should the demand arise.