Files
Abstract
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.