A Polyhedral Study of the Capacity Formulation of the Multilayer Network Design Problem

A multilayer network is a hierarchical network where each layer is built using the components of the previous one. Optical networks are an example of two layered networks. The multilayer network design problem consists of installing minimum cost integer capacities on the edges of all the layers so that a set of demands can be routed on the network. In this article, two versions of the optical network design problem are studied, and polyhedral results for the corresponding capacity formulations are presented.We also show how to extend the results to a network with an arbitrary number of layers.