Search

This chapter gives an insight into some challenging combinatorial optimization problems that have to be tackled to deliver efficient and appropriate decision algorithms to manage future networks. The first part of the chapter is dedicated to variants of routing optimization problems in future IP networks, and the second part is dedicated to two optimization problems related to network virtualization and 5G network slicing, the virtual network embedding problem and the service function chaining problem. Each of these optimization problems is described along with the main challenges to overcome, and a recent and extensive related state of the art is given, so as to highlight the most recent and promising approaches to solve them.

In this paper, we address the Unsplittable Non-Additive Capacitated Network Design problem, a variant of the Capacitated Network Design problem where the flow of each commodity cannot be split, even between two facilities installed on the same link. We propose a compact formulation and an aggregated formulation for the problem. The latter requires additional inequalities from considering each individual arc-set. Instead of studying those particular polyhedra, we consider a much more general object, the unitary step monotonically increasing set function polyhedra, and identify some families of facets. The inequalities that are obtained by specializing those facets to the Bin Packing function are separated in a Branch-and-Cut for the problem. Several series of experiments are conducted on random and realistic instances to give an insight on the efficiency of the introduced valid inequalities. HighlightsWe give two ILP formulations for the UNACND problem.We introduce polyhedra associated with a general class of functions.We provide two classes of facets that are valid for all considered functions.We devise a Branch-and-Cut algorithm embedding both classes of inequalities.Our approach gives promising results and shows the efficiency of our inequalities.

We consider the Capacitated Multi-Layer Network Design with Unsplittable demands (CMLND-U) problem. Given a two-layer network and a set of traffic demands, this problem consists in installing minimum cost capacities on the upper layer so that each demand is routed along a unique “virtual” path (even using a unique capacity on each link) in this layer, and each installed capacity is in turn associated a “physical” path in the lower layer. This particular hierarchical and unsplittable requirement for routing arises in the design of optical networks, including optical OFDM based networks. In this paper, we give an ILP formulation to the CMLND-U problem and we take advantage of its sub-problems to provide a partial characterization of the CMLND-U polytope including several families of facets. Based on this polyhedral study, we develop a Branch-and-Cut algorithm for the problem and show its effectiveness though a set of experiments, conducted on SNDlib-derived instances and also on real instances.

In this paper, we are interested in the Optical Multi-Band Network Design. This problem consists, given the physical layer of an optical network and a set of traffic demands, in designing a virtual layer and grooming the traffic demands on virtual links called subbands, then to determine the number of subbands and the wavelength to assign for each subband of the virtual layer. We first propose a node-arcs, and arc-paths integer linear programming formulations for the problem, then we describe the column generation procedure for solving the linear relaxation of the 0-1 arc-paths formulations.

In this paper we consider the traffic Grooming, Routing and Wavelength Assignment problem in optical WDM mesh networks. This is a network design problem which consists in grooming the demands in lightpaths, assigning a wavelength to each lightpath and routing the traffic on these lightpaths so that the total cost is minimum. We first give an Integer Linear Programming formulation for the problem. Then we discuss a preprocessing procedure for efficiently managing the existing resources of the network. We then propose a fast and effective heuristic for solving large and real instances of the problem. We finally provide an illustrative application of the proposed heuristic for a real backhaul network instance.