ON A BRANCH-AND-BOUND METHOD FOR SEPARABLE CONCAVE PROGRAMS.

A separable concave program is defined to be any program of the form Minimize zx subject to x in K, where K is any subset of n-space and zx is a separable concave function, i.e. can be written as a sum of n concave functions each of which depends on only one of the components of the vector x. A familiar special case is the so-called fixed charge linear program. It is shown how a branch-and-bound algorithm for a separable concave program can always be obtained if the related program of minimizing a linear function over K can be performed efficiently. A special case is considered in which K is a very large discrete set but can be described as the vector sum of smaller sets. The branch-and-bound algorithm for this special case has been programmed and applied to a problem of selecting a minimum cost fleet of space vehicles. Author