Flows in Arborescences

Fred Glover
Additional contact information
Fred Glover: University of Colorado

Management Science, 1971, vol. 17, issue 9, 568-586

Abstract: This paper gives efficient methods for solving four specially structured network problems that arise in connection with certain integer programming methods developed by Cook and Cooper, Hillier, and Glover. Such problems have also independently been studied in inventory theory by Ignall and Veinott, who have developed extensive qualitative (nonalgorithmic) implications of their structures. In the integer programming context, special subclasses of these network problems are generated and solved as part of a strategy for solving more general integer linear programs. By providing particularly efficient methods for accommodating somewhat broader network structures, our results enable the development of related integer programming solution strategies that generate more complex subproblems. We show that the first of the four network problems can be solved by a procedure that assigns each variable a value exactly once, without subsequent revision. Properties of optimal solutions for the remaining problems are developed that enable the algorithm for the first to be extended to the second and then, by suitable transformation of variables, to the third and last problems as well. Moreover, while the last three problems involve an additional linear constraint that nullifies the "integer extreme point property," we show that optimal integer solutions to these problems can nevertheless easily be obtained from the optimal continuous solutions.

Date: 1971
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.17.9.568 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:17:y:1971:i:9:p:568-586

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().