Virtual Network Embedding (VNE) is an optimization problem at the core of many modern network telecommunication technologies related to the implementation of virtual networks, such as Network Slicing. The VNE problem consists in finding an optimal assignment of virtual demands to physical resources, encompassing simultaneous placement and routing decisions.We study the offline version of the VNE, which arises in the context of decision-making for resource allocation and network slice planning. For large networks, the heuristics of the literature often struggle to find solutions, especially when available resources (on nodes and edges) are sparse.To address these challenges, we explore mathematical programming approaches. Since the classical Flow Formulation provides a weak linear relaxation, we consider a novel formulation, based on a partition of the virtual graph into smaller virtual subgraphs. Since this formulation has an exponential number of variable, its linear relaxation can be solved with Column Generation. We devise a Price-Branch heuristic able to solve large instances, while providing optimality gap. The resulting computational experiments indicate our Price-Branch heuristic is often the only algorithm able to find a solution from a certain instance size, largely outperforming the Flow Formulation or literature heuristics.

In this paper, we characterize in several manners the class of contraction perfect graphs which are the perfect graphs that remain perfect after the contraction of any edge set. We define the utter graph u ( G ) which is the graph whose stable sets are in bijection with the co-2-plexes of G , and prove that u ( G ) is perfect if and only if G is contraction perfect. Moreover, we exhibit the strong link between co-2-plexes and induced matchings and discuss its consequences according to known results on these problems. This yields several classes of graphs for which the maximum weighted co-2-plex is solvable in polynomial time. Finally, we show how our results extend to a new class of graphs for which finding a maximum weighted induced matching can be done in polynomial time.

Abstract The survivable hierarchical telecommunications network design problem consists of locating concentrators, assigning user nodes to concentrators, and linking concentrators in a reliable backbone network. In this article, we study this problem when the backbone is 2‐edge connected and when user nodes are linked to concentrators by a point‐to‐point access network. We formulate this problem as an integer linear program and present a facial study of the associated polytope. We describe valid inequalities and give sufficient conditions for these inequalities to be facet defining. We investigate the computational complexity of the corresponding separation problems. We propose some reduction operations to speed up the separation procedures. Finally, we devise a branch‐and‐cut algorithm based on these results and present the outcome of a computational study. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

In this paper, we present procedures to obtain facet-defining inequalities for the independence system polytope. These procedures are defined for inequalities which are not necessarily rank inequalities. We illustrate the use of these procedures by deriving strong valid inequalities for the acyclic induced subgraph, triangle free induced subgraph, bipartite induced subgraph, and knapsack polytopes. Finally, we derive a new family of facet-defining inequalities for the independence system polytope by adding a set of edges to antiwebs.