Search

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.

We investigate a variant of the Multi-Layer Network Design problem where minimum cost capacities have to be installed upon a virtual layer in such a way that (i) a set of traffic demands can be routed AND (ii) each capacity (subband) is assigned a route in the physical layer. The traffic demands cannot be splitted along several paths (nor even several capacities installed on the same link), which makes the problem even more difficult. In this paper, we present new non-compact ILP formulations to model the problem and provide column generation procedures, based on different Dantzig-Wolfe decomposition schemes to solve it. More precisely, an arc-flow formulation is given for the problem and used to derive two different paths formulations: non-aggregated and aggregated. The former contains two families of path variables and requires a double column generation procedure to solve it, while the latter relies on a single path variable with a specific structure. These alternative modeling approaches induce two Branch-and-Price algorithms that allow to solve the problem efficiently for several classes of instances.

International audience; In this paper, we consider the Capacitated Network Design (CND) problem. We investigate the relationship between CND and the Bin-Packing problem. This is exploited for identifying new classes of valid inequalities for the CND problem and developing a branch-and-cut algorithm to solve it efficiently.

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.