# 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):

# Report Date:

## 1967-07-01

# Pagination or Media Count:

## 61.0

# 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:

# Subject Categories:

- Operations Research