MULTI-COMMODITY NETWORK SOLUTIONS.
OPERATIONS RESEARCH CENTER UNIV OF CALIF BERKELEY
Pagination or Media Count:
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
- Operations Research