  This paper considers the network slicing (NS) problem which attempts to map
multiple customized virtual network requests to a common shared network
infrastructure and allocate network resources to meet diverse service
requirements. This paper proposes an efficient decomposition algorithm for
globally solving the large-scale NP-hard NS problem. The proposed algorithm
decomposes the hard NS problem into two relatively easy function placement (FP)
and traffic routing (TR) subproblems and iteratively solves them enabling the
information feedback between each other, which makes it particularly suitable
to solve large-scale problems. Specifically, the FP subproblem is to place
service functions into cloud nodes in the network, and solving it can return a
function placement strategy based on which the TR subproblem is defined; and
the TR subproblem is to find paths connecting two nodes hosting two adjacent
functions in the network, and solving it can either verify that the solution of
the FP subproblem is an optimal solution of the original problem, or return a
valid inequality to the FP subproblem that cuts off the current infeasible
solution. The proposed algorithm is guaranteed to find the global solution of
the NS problem. By taking the special structure of the NS problem into
consideration, we successfully develop two families of valid inequalities that
render the proposed decomposition algorithm converge much more quickly and thus
much more efficient. We demonstrate the effectiveness and efficiency of the
proposed valid inequalities and algorithm via numerical experiments.
