Accession Number : AD0663680

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

Corporate Author : BOEING SCIENTIFIC RESEARCH LABS SEATTLE WASH MATHEMATICS RESEARCH LAB

Personal Author(s) : Walkup,D. W.

Report Date : SEP 1967

Pagination or Media Count : 21

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)

Descriptors :   (*MATHEMATICAL PROGRAMMING, PROBLEM SOLVING), LINEAR PROGRAMMING, ALGORITHMS, OPTIMIZATION, COSTS, SET THEORY, INEQUALITIES, THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE