Optimal design of a covering network

This paper considers the covering network design problem (CNDP). In the CNDP, an undirected graph is given where nodes correspond to potential facility sites and arcs to potential links connecting facilities. The objective of the CNDP is to identify the least cost connected subgraph whose nodes can cover the given demand points. The problem defines a demand point to be covered if some node in the selected graph is present within an appropriate distance from the demand point. The paper presents an integer programming formulation for the problem and develops a dual-based solution procedure. The computational results for randomly generated test problems are also shown [In Korean.]