A MIP-based Heuristic Approach to solve a Prize-Collecting Local Access Network Design Problem

This paper presents a new combinatorial optimization problem that can be used to model the deployment of broadband telecommunications systems in which optical fiber cables are installed between a central office and a number of end-customers. In this capacitated network design problem the installation of optical fiber cables with sufficient capacity is required to carry the traffic from the central office to the end-customers at minimum cost. In the situation motivating this research the network does not necessarily need to connect all customers (or at least not with the best available technology). Instead, some nodes are potential customers. The aim is to select the customers to be connected to the central server and to choose the cable capacities to establish these connections. The telecom company takes the strategic decision of fixing a percentage of customers that should be served, and aims for minimizing the total cost of the network providing this minimum service. For that reason the underlying problem is called the Prize-Collecting Local Access Network Design problem (PC-LAN). We propose a branch-and-cut approach for solving small instances. For large instances of practical importance, our approach turns into a mixed integer programming (MIP) based heuristic procedure which combines the cutting-plane algorithm with a multi-start heuristic algorithm. The multi-start heuristic algorithm starts with fractional values of the LP-solutions and creates feasible solutions that are later improved using a local improvement strategy. Computational experiments are conducted on small instances from the literature. In addition, we introduce a new benchmark set of real-world instances with up to 86,000 nodes, 116,000 edges and 1500 potential customers. Using our MIP-based approach we are able to solve most of the small instances to proven optimality. For more difficult instances, we are not only able to provide high-quality feasible solutions, but also to provide certificate on their quality by calculating lower bounds to the optimal solution values. Link to the article

LJUBIC, I., PUTZ, P. and SALAZAR-GONZALEZ, J.J. (2014). A MIP-based Heuristic Approach to solve a Prize-Collecting Local Access Network Design Problem. European Journal of Operational Research, 235(3), pp. 727-739.

Keywords : #Network-loading, #Local-access, #Prize, #collecting, #Matheuristic-algorithm