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.