FLOWS IN ARBORESCENCES.
CARNEGIE INST OF TECH PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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
- Operations Research