
Accession Number : AD0663680
Title : ON A BRANCHANDBOUND 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 nspace 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 socalled fixed charge linear program.) It is shown how a branchandbound 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 branchandbound 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