ON A BRANCH-AND-BOUND METHOD FOR SEPARABLE CONCAVE PROGRAMS.
Abstract
A separable concave program is defined to be any program of the form: Minimize z(x) subject to x in K, where K is any subset of n-space and z(x) 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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1967
- Accession Number
- AD0663680
Entities
People
- D. W. Walkup
Organizations
- Boeing