Article ID: | iaor201522258 |
Volume: | 64 |
Issue: | 2 |
Start Page Number: | 65 |
End Page Number: | 75 |
Publication Date: | Sep 2014 |
Journal: | Networks |
Authors: | Granot Frieda, Ciurria-Infosino Iara, Veinott Arthur F |
Keywords: | networks, combinatorial optimization, networks: flow |
We examine in this article when it is possible to predict, without numerical computation, the direction of change of optimal multicommodity flows on suspension graphs resulting from changes in arc‐commodity parameters. Using results of Evans (Oper Res 26 (1978), 673–679) and of Soun and Truemper (SIAM J Algebr Discrete Meth 1 (1980), 348–358), the multicommodity flow problem on a graph that is two‐isomorphic to a suspension graph is reduced to a single‐commodity flow problem on an enlarged graph, called a ‘rolodex graph.’ Such a reduction allows us to apply results of Granot and Veinott (Math Oper Res 10 (1985), 471–497), developed for single‐commodity network‐flow problems, to derive qualitative sensitivity analysis results for multicommodity flow problems on graphs which are two‐isomorphic to suspension graphs.