In this paper we investigate the nature of integer solutions to multicommodity network flow problems from a graphtheoretic viewpoint. A sufficient condition for unimodularity is developed that is based upon the topological characteristics of the associated graph, and the results are applied to certain well-structured examples.

References

1 Camion, P., “Characterization of Totally Unimodular Matrices,” Proc. Amer. Math. Soc., 16, 1965, pp. 1068–1073.
Web of Science® Google Scholar
2 Commoner, F. G., “A Sufficient Condition for a Matrix to be Totally Unimodular,” Networks, 3, 1973, pp. 351–365.
10.1002/net.3230030406
Google Scholar
3 Dantzig, G. B., Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey, 1963.
10.1515/9781400884179
Web of Science® Google Scholar
4 Evans, J. R., “A Combinatorial Equivalence Between a Class of Multicommodity Flow Problems and the Capacitated Transportation Problem,” Math. Prog., 10, 1976, pp. 141–144.
10.1007/BF01580684
Web of Science® Google Scholar
5 Evans, J. R., “ A Single Commodity Network Model for a Class of Multicommodity Dynamic Planning Problems,” Working Paper, Department of Quantitative Analysis, University of Cincinnati, 1975.
Google Scholar
6 Evans, J. R., “A Single Commodity Transformation for Certain Multicommodity Networks,” Opns. Res., to appear.
Google Scholar
7 Evans, J. R., “Some Network Flow Models and Heuristics for Multiproduct Production and Inventory Planning,” AIIE Trans., 9, 1977, pp. 75–81.
10.1080/05695557708975124
Web of Science® Google Scholar
8 Evans, J. R., “The Simplex Method for Integral Multicommodity Networks,” Naval Res. Logist. Quart., to appear.
Google Scholar
9 Evans, J. R., J. J. Jarvis and R. A. Duke, “Graphic Matroids and the Multicommodity Transportation Problem,” Math. Prog., 13, 1977, pp. 323–328.
10.1007/BF01584345
Web of Science® Google Scholar
10 Grigoriadis, M. D. and W. W. White, “A Partitioning Algorithm for the Multicommodity Network Flow Problem,” Math. Prog., 3, 1972, pp. 157–177.
10.1007/BF01584987
Google Scholar
11 Hartman, J. K. and L. S. Lasdon, “A Generalized Upper Bounding Algorithm for Multicommodity Network Flow Problems,” Networks, 1, 1972, pp. 333–354.
10.1002/net.3230010404
Google Scholar
12 Heller, I., “On Linear Systems with Integral Valued Solutions,” Pac. J. Math., 7, 1957, pp. 1351–1364.
10.2140/pjm.1957.7.1351
Google Scholar
13 Heller, I. and A. J. Hoffman, “On Unimodular Matrices,” Pac. J. Math., 12, 1962, pp. 1321–1327.
10.2140/pjm.1962.12.1321
Web of Science® Google Scholar
14 Hoffman, A. J. and J. B. Kruskal, “ Integral Boundary Points of Convex Polyhedra,” Linear Inequalities and Related Systems, H. W. Kuhn, and A. W. Tucker, eds., Princeton University Press, Princeton, New Jersey, 1967.
Google Scholar
15 Johnson, E. L., “ Programming in Networks and Graphs,” ORC-65-1, University of California, Berkeley, 1965.
Google Scholar
16 Kennington, J. L. and M. Shalaby, “An Effective Subgradient Procedure for Minimal Cost Multicommodity Flow Problems,” Man. Sci., 23, 1977, pp. 994–1004.
10.1287/mnsc.23.9.994
Web of Science® Google Scholar
17 Liu, C. L., Introduction to Combinatorial Mathematics, McGraw Hill, New York, 1968.
Google Scholar
18 Truemper, K., “ Algebraic Characterizations of Totally Unimodular Matrices: A Framework,” Working Paper, University of Texas at Dallas, 1975.
Google Scholar
19 Truemper, K., “ Algebraic Characterizations of Unimodular Matrices,” Working Paper, University of Texas at Dallas, 1975.
Google Scholar
20 Truemper, K., “Unimodular Matrices of Flow Problems with Additional Constraints,” Networks, 7, 1977, pp. 343–358.
10.1002/net.3230070406
Web of Science® Google Scholar
21 Veinott, A. F. and G. B. Dantzig, “Integral Extreme Points,” SIAM Review, 10, 1968, pp. 371–372.
10.1137/1010063
Web of Science® Google Scholar

Citing Literature

Volume8, Issue2

Summer 1978

Pages 107-119

Network topology and integral multicommodity flow problems

Abstract

References

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Network topology and integral multicommodity flow problems

Abstract

References

Citing Literature

References

Related

Information