Layered Graph Approaches to the Hop Constrained Connected Facility Location Problem
Given a set of customers, a set of potential facility locations, and some interconnection nodes, the goal of the connected facility location problem (ConFL) is to find the minimum-cost way of assigning each customer to exactly one open facility and connecting the open facilities via a Steiner tree. The sum of costs needed for building the Steiner tree, facility opening costs, and the assignment costs needs to be minimized. If the number of edges between a prespecified node (the so-called root) and each open facility is limited, we speak of the hop constrained facility location problem (HC ConFL). This problem is of importance in the design of data-management and telecommunication networks. In this article we provide the first theoretical and computational study for this new problem that has not been studied in the literature so far. We propose two disaggregation techniques that enable the modeling of HC ConFL: (i) as a directed (asymmetric) ConFL on layered graphs, or (ii) as the Steiner arborescence problem (SA) on layered graphs. This allows for usage of best-known mixed integer programming models for ConFL or SA to solve the corresponding hop constrained problem to optimality. In our polyhedral study, we compare the obtained models with respect to the quality of their linear programming lower bounds. These models are finally computationally compared in an extensive computational study on a set of publicly available benchmark instances. Optimal values are reported for instances with up to 1,300 nodes and 115,000 edges.
connected facility location mixed integer programming models hop constrained minimum spanning trees hop constrained steiner trees lp-relaxations