Accession Number : AD0639672

Title :   MULTI-COMMODITY NETWORK SOLUTIONS.

Descriptive Note : Research rept.,

Corporate Author : OPERATIONS RESEARCH CENTER UNIV OF CALIF BERKELEY

Personal Author(s) : Jewell,William S.

Report Date : SEP 1966

Pagination or Media Count : 18

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)

Descriptors :   (*OPERATIONS RESEARCH, *COMBINATORIAL ANALYSIS), (*LINEAR PROGRAMMING, *GRAPHICS), NETWORKS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE