Designing Private Line Networks- Polyhedral Analysis and Computation.

We study a capacitated network design problem arising in the design of private line network. Given a complete graph, a subset of its node set ( the "hub" set), and point-to-point traffic demands, the objective is to install capacity on the edges (using several batch sizes and nonlinear costs), and route traffic in the resulting capacitated network so that 1) all demand between a pair of nodes is routed along a sing;e path, and 2) the demand is either set directly from source to sink, or via a numder of hub nodes.