FLOWS IN ARBORESCENCES.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1967
- Accession Number
- AD0656626
Entities
People
- Fred Glover
Organizations
- Carnegie Institute of Technology