A Combinatorial Optimisation Approach to Designing Dual-Parented
  Long-Reach Passive Optical Networks
  We present an application focused on the design of resilient long-reach
passive optical networks. We specifically consider dual-parented networks
whereby each customer must be connected to two metro sites via local exchange
sites. An important property of such a placement is resilience to single metro
node failure. The objective of the application is to determine the optimal
position of a set of metro nodes such that the total optical fibre length is
minimized. We prove that this problem is NP-Complete. We present two
alternative combinatorial optimisation approaches to finding an optimal metro
node placement using: a mixed integer linear programming (MIP) formulation of
the problem; and, a hybrid approach that uses clustering as a preprocessing
step. We consider a detailed case-study based on a network for Ireland. The
hybrid approach scales well and finds solutions that are close to optimal, with
a runtime that is two orders-of-magnitude better than the MIP model.
