An access network design problem with end-to-end QoS constraints

• We describe a novel nonlinear MIP modeling approach for solving an access network design problem.
• Exploiting the inherent combinatorial structure of QoS limits, we devise bounding strategies.
• We develop effective constraint generation algorithms within the context of branch and cut.
• Computational experiments demonstrate the effectiveness of the proposed solution procedures.

In this paper, we present an access network design problem with end-to-end quality of service (QoS) requirement. The problem can be conceptualized as a two-level hierarchical location-allocation problem on the tree topology with nonlinear side constraints. The objective function of the nonlinear mixed integer programming model minimizes the total cost of switch and fiber cable, while satisfying demand within the prescribed level of QoS. By exploiting the inherent structure of the nonlinear QoS constraints, we develop linearization techniques for finding an optimal solution. Also, we devise an effective exact optimal algorithm within the context of disjunctive constraint generation. We present promising computational results that demonstrate the effectiveness of the proposed solution procedure.