MULTI-COMMODITY NETWORK SOLUTIONS.
Abstract
Multicommodity network flow problems have rational optimal solutions, in general, because the constraint matrix is not unimodular. Thus, all algorithms proposed to date require solving the equivalent of a general linear program in order to allocate the mutual capacities correctly, and it is here that fractional solutions may arise. This paper attempts to characterize the nature of these rational solutions by presenting several conjectures about the 'modularity' of multicommodity flow problems. Fundamental differences between the directed- and undirected-arc case are revealed, as well as the important role played by individual capacity constraints. Further investigations seems to require the development of new combinatorial and graph-theoretic methods. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1966
- Accession Number
- AD0639672
Entities
People
- William S. Jewell