查看文章

In this paper we discuss compact models for a hop-constrained node survivable network design problem. We discuss two models involving one set of variables associated to each path between each pair of demand nodes (a standard network flow model with additional cardinality constraints and a model with hop-indexed variables) and a third model involving one single set of hop-indexed variables for each demand pair. We show that the aggregated more compact hop-indexed model produces the same linear programming bound as the multi-path hop-indexed model. This work is given in the context of the following MPLS network design problem. Given the location of edge nodes, the candidate locations of core nodes and the pairs of locations that can be physically connected, the MPLS network design problem addressed in this paper is the determination of the physical network topology, i.e., the location …