  Network design, a cornerstone of mathematical optimization, is about defining
the main characteristics of a network satisfying requirements on connectivity,
capacity, and level-of-service. It finds applications in logistics and
transportation, telecommunications, data sharing, energy distribution, and
distributed computing. In multi-commodity network design, one is required to
design a network minimizing the installation cost of its arcs and the
operational cost to serve a set of point-to-point connections. The definition
of this prototypical problem was recently enriched by additional constraints
imposing that each origin-destination of a connection is served by a single
path satisfying one or more level-of-service requirements, thus defining the
Network Design with Service Requirements [Balakrishnan, Li, and Mirchandani.
Operations Research, 2017]. These constraints are crucial, e.g., in
telecommunications and computer networks, in order to ensure reliable and
low-latency communication. In this paper we provide a new formulation for the
problem, where variables are associated with paths satisfying the end-to-end
service requirements. We present a fast algorithm for enumerating all the
exponentially-many feasible paths and, when this is not viable, we provide a
column generation scheme that is embedded into a branch-and-cut-and-price
algorithm. Extensive computational experiments on a large set of instances show
that our approach is able to move a step further in the solution of the Network
Design with Service Requirements, compared with the current state-of-the-art.
