Y. K. Agarwal, Sachin Jayaswal
We study the problem of the optimal design of fiber-to-the-home (FTTH) optical access networks. Given a network of nodes and edges rooted at an optical distribution point (ODP) with a given demand for optical fibers at a subset of these nodes, the problem entails finding the optimal placement of splitters, which allows multiple demand points to share a common fiber between ODP and a splitter, such that sum of the costs of the fiber cables and the splitters is minimized. Additionally, it needs to decide on the optimal selection of a cable type of appropriate capacity on each edge of the network to carry the required traffic. The existing literature on FTTH access network design typically assumes the same number of splitting stages for all demand points—specifically, one in case of a single splitting problem (SSP) or two in case of a double splitting problem (DSP). We provide a mixed-integer programming (MIP) formulation of a mixed splitting problem (MSP), wherein some demand points can be served through one stage of splitting, whereas others can be served through two stages of splitting. We further propose several valid inequalities (VIs), with or without a pre-specified template, to strengthen the formulation. Through our computational experiments on large instances, we demonstrate the efficacy of our proposed VIs, which help improve the lower bound of the problem from 79% to 86.9% of the MIP optimal cost, on average. For the special cases of SSP and DSP, we show that our formulation produces much tighter lower bounds compared to the existing formulation in the literature. On top of that, our proposed VIs are comparatively much more effective in tightening the bounds. Specifically, our proposed formulation with our VIs consistently outperforms that available in the literature, being as much as 500 times faster in some instances.
