Quadratic P-Median Formulations with Connectivity Costs Between Facilities

In this paper, we consider the problem of minimizing simultaneously the total connectivity cost of a set of users to a set of facility nodes and between facilities themselves. The problem arises as an extension of the p-Median problem, which is a classical combinatorial optimization problem. We propose two mixed-integer quadratic programming models which allow obtaining optimal solutions. Example application domains where the proposed models can be utilized include modeling and management of smart transportation and wireless networks, to name a few. Our first model is derived as an extension of the classical p-Median formulation. Whereas the second one is an alternative set-covering model. Finally, we linearize these models and strengthen them by imposing additional linearized quadratic cuts. We solve hard instances with up to 60 facility nodes and 350 users with the Gurobi solver. Our preliminary numerical results indicate that the linear set-covering formulation allows solving all tested instances to optimality in significantly less computational effort, which is not possible to achieve with the other proposed models. © 2021, Springer Nature Switzerland AG.