01487908

a

01487908 Holmberg, Kaj Yuan, Di On extended models of multicommodity routing with side constraints on paths. Kall, Peter (ed.) et al., Operations research proceedings 1998. Selected papers of the 4th annual international conference, OR98 held in Z\"urich, Switzerland, August 31-September 3, 1998. Berlin: Springer. 411-420 (1999). 1999 Berlin: Springer EN multicommodity routing network flow side constraints Summary: A commonly used model for routing in communication networks is the linear Multicommodity Network Flow (MCNF) model, in which a commodity is defined by a communication pair, also known as an O-D pair. In the basic MCNF model, there is no restriction on which paths that can be used for routing. In telecommunication networks, there are often restrictions on which paths that are permitted to use for each O-D pair, due to time delay and/or reliability requirements. We extend the basic MCNF model by including side constraints on paths. Two extended models with different objectives are studied. In the first model, the cost function is linear in the flow variables. This model can be efficiently solved by a tailored column generation approach. In the second model, the routing consideration is based on the longest path used for each O-D pair and leads to an objective function of min-max type. We clarify the relations between these two models and discuss bounding procedures for the second model. Some computational results are presented.