Accession Number : AD0656626

Title :   FLOWS IN ARBORESCENCES.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE INST OF TECH PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Glover,Fred

Report Date : JUL 1967

Pagination or Media Count : 61

Abstract : Efficient algorithms are given for four network flow problems that arise in solving integer programs by truncated enumeration. The first problem is to find a maximum weight (or minimum cost) flow in an arborescence with upper and lower bound capacities on each arc. Each of the remaining three problems is to find a maximum or minimum flow across some arc of the arborescence (respectively, the terminal arc, a source arc, or an intermediate arc), such that the total weight of the flow is not less than a specified value. Theorems are given characterizing the properties of optimal solutions to these problems, providing the basis for the algorithms proposed. Necessary and sufficient feasibility criteria are provided for the first problem, and a theorem is also given characterizing the relation between optimal integer and continuous solutions to the last three problems. A numerical example is solved in the concluding section. (Author)

Descriptors :   (*LINEAR PROGRAMMING, ALGORITHMS), OPTIMIZATION, INEQUALITIES, TRANSFORMATIONS(MATHEMATICS), SET THEORY, THEOREMS, MATHEMATICAL ANALYSIS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE