Keywords

1 Introduction

The p-Median problem is a classical combinatorial optimization problem which can be described as follows. First, we are given a set of facility nodes \(\mathcal {J}\) and a set of users (customers) \(\mathcal {I}\) with cardinalities n and m, respectively. Then, the problem consists of finding an optimal subset of facility nodes \(\mathcal {P}\subseteq \mathcal {J}\) with cardinality p that minimizes the total connectivity cost in such a way that each user of \(\mathcal {I}\) is assigned to a unique facility node in \(\mathcal {P}\). It is a discrete type location problem with many real-life applications including the location of industrial plants, warehouses, public facilities, and network design problems, to name a few [1, 8]. In particular, for network design problems, it provides a useful modeling framework as it allows forming backbone network structures [1, 2, 8, 9].

In this paper, we consider the problem of minimizing simultaneously the total connectivity cost of users to facilities, as in the classical p-Median problem, plus the total connectivity cost between pairs of facilities. Notice that the latter cost is not usually incorporated in the classical p-Median problem. We argue that the motivation for doing so can be justified within many application domains. For example, when moving patients from one hospital to another one under pandemic situations like covid-19. Similarly, in a wireless network, it is highly required that the facilities forming a backbone network structure are installed as close as possible since this would allow more rapid transmission of the data and at lower power consumption. Notice that even though the proposed models provide a generic modeling framework, they can be straightforwardly applied and adapted to many optimization problems related to smart transportation and wireless networks [1]. Also notice that in a graph layout configuration of a network, the connectivity cost between two facilities can be computed as a function of the shortest path distance between them [5]. We propose two mixed-integer quadratic programming models. The first one is derived as an extension of the classical p-Median formulation. Whereas the second one is formulated based on an alternative set-covering formulation related to the p-Median problem [3]. Then, we apply the Fortet linearization method [6] and obtain two additional mixed-integer linear programming (MIP) models. Finally, each linearized model is further strengthened by imposing additional linearized quadratic cuts. In particular, we derive a cardinality cut that allows tightening the linear programming relaxations significantly.

As far as we know, our proposed models are new to the literature. A similar problem was studied in [10] where the author reports a new integer quadratic formulation of a general hub-location problem. The author discusses a variety of alternative solution strategies and proposes two heuristics for the task of siting 2, 3, or 4 hubs to serve interactions between sets of 10, 15, 20, and 25 cities. Other related works, from the domain of wireless networks and urban planning, where our proposed formulations can be applied, are reported in references [7, 11]. In particular, in [7], the author proposes a distribution location plan for multi-sink nodes in a wireless sensor network based on the p-median problem. The author also proposes a heuristic algorithm and shows that the proposed strategy can effectively reduce the overall energy consumption, improve the efficiency of the network service and extend the network lifetime. Analogously, in [11], the authors incorporate big data in urban planning for better modeling of urban dynamics and more efficiently allocating limited resources. The authors propose a high-performance computing-based algorithm based on random sampling and spatial voting techniques to solve large-sized p-median problems. Numerical results show that their proposed algorithm provides high-quality solutions and reduces computing time significantly. They also demonstrate the dynamic scalability of their proposed algorithm.

The paper is organized as follows. In Sect. 2, we present and explain the quadratic and linear mathematical formulations. Then, we explain how we derive quadratic cuts, which allow tightening each of the linear programming (LP) relaxations. Subsequently, in Sect. 3, we conduct preliminary numerical experiments in order to compare all the proposed models. Finally, in Sect. 4, we present our main conclusions and provide some insight for future research.

2 Mathematical Formulations and Quadratic Cuts

In this section, we first present and explain the proposed mixed-integer quadratic and linear models. Then, we describe how we obtain the quadratic cuts, which are added to the MIP models.

2.1 Proposed Mathematical Formulations

In order to write a first quadratic model, we define the following binary variables

$$\begin{aligned} y_{j}= \left\{ \begin{array}{ll} 1, &{} \hbox { if facility node}\, j \in \mathcal {J}\; \hbox {belongs to subset}\, \mathcal {P}. \\ 0, &{} \hbox { otherwise.} \end{array} \right. \end{aligned}$$

and

$$\begin{aligned} x_{ij}= \left\{ \begin{array}{ll} 1, &{} \hbox { if user}\, i \in \mathcal {I}\; \hbox {is assigned to facility node}\, j\in \mathcal {J}. \\ 0, &{} \hbox { otherwise.} \end{array} \right. \end{aligned}$$

We also define the input matrices \(C=(C_{ij})\) for all \(i \in \mathcal {I}\) and \(j \in \mathcal {J}\), and \(D=(D_{ij})\) for all \(i,j \in \mathcal {J}\) as the required distance matrices. Notice that each entry in each of these input matrices represents the distance between elements i and j. Consequently, a first model can be written as follows

$$\begin{aligned} Q_1: \min _{\{x,y\}}&\sum _{i \in \mathcal {I}}\sum _{j \in \mathcal {J}} C_{ij}x_{ij}+\sum _{i \in \mathcal {J}}\sum _{\begin{array}{c} j \in \mathcal {J}\\ (i \ne j) \end{array}} \frac{1}{2}D_{ij}y_{i}y_{j} \end{aligned}$$
(1)
$$\begin{aligned} \text{ s.t.: }&\sum _{j \in \mathcal {J}} x_{ij} = 1, \quad \forall i \in \mathcal {I} \end{aligned}$$
(2)
$$\begin{aligned}&\sum _{j \in \mathcal {J}} y_{j} = p \end{aligned}$$
(3)
$$\begin{aligned}&x_{ij} \le y_{j}, \quad \forall i \in \mathcal {I}, j \in \mathcal {J} \end{aligned}$$
(4)
$$\begin{aligned}&x \in \{0,1\}^{mn}, y \in \{0,1\}^{n} \end{aligned}$$
(5)

where the first and second terms in the objective function (1) represent the connectivity costs between users and facilities, and between facilities themselves, respectively. The constraints (2) ensure that each user \(i \in \mathcal {I}\) is connected to a unique facility node \(j \in \mathcal {J}\). Next, the constraint (3) is used to select p out of n facilities from \(\mathcal {J}\). Subsequently, the constraints (4) ensure that each user \(i \in \mathcal {I}\) is connected to a facility node \(j \in \mathcal {J}\) if and only if j is active. Finally, constraints (5) are the domain constraints for the decision variables.

In order to obtain an equivalent MIP formulation for \(Q_1\), we apply the Fortet linearization method [6]. This method consists of replacing each quadratic term in the objective function (1) with a new variable \(z_{ij}=y_{i}y_{j}\) for all \(i,j \in \mathcal {J},(i<j)\) while simultaneously adding linearization constraints. This leads to the following equivalent MIP model

$$\begin{aligned} M_1: \min _{\{x,y,z\}}&\sum _{i \in \mathcal {I}}\sum _{j \in \mathcal {J}} C_{ij}x_{ij}+\sum _{i \in \mathcal {J}}\sum _{\begin{array}{c} j \in \mathcal {J}\\ (i < j) \end{array}} D_{ij}z_{ij}\end{aligned}$$
(6)
$$\begin{aligned} \text{ s.t.: }&(2)-(4) \nonumber \\&z_{ij} \le y_{i}, \quad \forall i, j \in \mathcal {J}, (i<j) \end{aligned}$$
(7)
$$\begin{aligned}&z_{ij} \le y_{j}, \quad \forall i, j \in \mathcal {J}, (i<j) \end{aligned}$$
(8)
$$\begin{aligned}&z_{ij} \ge y_{i}+y_{j}-1, \quad \forall i, j \in \mathcal {J}, (i<j) \end{aligned}$$
(9)
$$\begin{aligned}&x \in \{0,1\}^{mn}, y \in \{0,1\}^{n}, z \in \{0,1\}^{\frac{n(n-1)}{2}}, \end{aligned}$$
(10)

where the objective function (6) is no longer a quadratic one, but a linear one. The constraints (7)–(9) are the linearization constraints and ensure that variable \(z_{ij}=1\) if and only if both \(y_{i}=y_{j}=1\) for all \(i,j \in \mathcal {J},(i<j)\). Otherwise, if either \(y_{i}\) or \(y_{j}\) equals zero, then \(z_{ij}=0\). Notice that we do not use both variables \(z_{ij}\) and \(z_{ji}\) in \(M_1\) as each connection link is considered only once.

In order to write an equivalent set-covering formulation, we first add an artificial facility node to set \(\mathcal {J}\). Denote this new set by \(\mathcal {\hat{J}}\). Next, we define an additional input matrix \(\hat{C}=(\hat{C}_{ij})\) for each \(i \in \mathcal {I}\) and \(j \in \mathcal {\hat{J}}\). This new extended matrix is constructed as follows. First, let \(\hat{C}\) be an empty matrix. Then, for each \(i \in \mathcal {I}\), we sort in ascending order the corresponding row vector of matrix \(C=(C_{ij})\), for all \(j \in \mathcal {J}\) and add the resulting sorted vector to the \(i_{th}\) row of matrix \(\hat{C}\). Finally, we add an extra zero column vector to the left of matrix \(\hat{C}\). Similarly, we define the input symmetric matrix \(\hat{D}=(\hat{D}_{ij})\) for all \(i,j \in \mathcal {\hat{J}}\). This matrix \(\hat{D}\) is constructed by adding zero column and row vectors to the left and at the top of matrix D, respectively. To terminate, we define the following cumulative variables

$$\begin{aligned} w_{ij}= \left\{ \begin{array}{ll} 1, &{} \hbox { if the distance cost of user}\, i \in \mathcal {I}\; \hbox {is at least}\, \hat{C}_{ij},\, \hbox {for all}\, j\in \mathcal {\hat{J}}\\ &{} \hbox { no matter which median it is allocated to.} \\ 0, &{} \hbox { otherwise.} \end{array} \right. \end{aligned}$$

Thus, a quadratic p-Median formulation can now be written as

$$\begin{aligned} Q_2: \min _{\{w,y\}}&\sum _{i \in \mathcal {I}}\sum _{j \in \mathcal {\hat{J}}\setminus \{1\} } (\hat{C}_{ij}-\hat{C}_{i,j-1})w_{ij}+\sum _{i \in \mathcal {\hat{J}}\setminus \{1\}}\sum _{\begin{array}{c} j \in \mathcal {\hat{J}}\setminus \{1\}\\ (i \ne j) \end{array}} \frac{1}{2}\hat{D}_{ij}y_{i}y_{j} \end{aligned}$$
(11)
$$\begin{aligned} \text{ s.t.: }&\sum _{ j \in \mathcal {\hat{J}}\setminus \{1\} } y_{j} = p \end{aligned}$$
(12)
$$\begin{aligned}&w_{ik}+\sum _{ \begin{array}{c} j \in \mathcal {\hat{J}}\setminus \{1\}\\ \{C_{ij} < \hat{C}_{ik}\} \end{array} } y_{j} \ge 1, \quad \forall i \in \mathcal {I}, k \in \mathcal {\hat{J}}\setminus \{1\}\end{aligned}$$
(13)
$$\begin{aligned}&w \in \{0,1\}^{m(n+1)}, y \in \{0,1\}^{n+1} \end{aligned}$$
(14)

Analogously as for \(Q_1\), we can obtain its linearized version as

$$\begin{aligned} M_2: \min _{\{w,y,z\}}&\sum _{i \in \mathcal {I}}\sum _{j \in \mathcal {\hat{J}}\setminus \{1\} } (\hat{C}_{ij}-\hat{C}_{i,j-1})w_{ij}+\sum _{i \in \mathcal {\hat{J}}\setminus \{1\}}\sum _{\begin{array}{c} j \in \mathcal {\hat{J}}\setminus \{1\}\\ (i < j) \end{array}} \hat{D}_{ij}z_{ij} \end{aligned}$$
(15)
$$\begin{aligned} \text{ s.t.: }&(12)-(13) \nonumber \\&z_{ij} \le y_{i}, \quad \forall i, j \in \mathcal {\hat{J}}\setminus \{1\}, (i<j) \end{aligned}$$
(16)
$$\begin{aligned}&z_{ij} \le y_{j}, \quad \forall i, j \in \mathcal {\hat{J}}\setminus \{1\}, (i<j) \end{aligned}$$
(17)
$$\begin{aligned}&z_{ij} \ge y_{i}+y_{j}-1, \quad \forall i, j \in \mathcal {\hat{J}}\setminus \{1\}, (i<j) \end{aligned}$$
(18)
$$\begin{aligned}&w \in \{0,1\}^{m(n+1)}, y \in \{0,1\}^{n+1}, z \in \{0,1\}^{\frac{(n+1)n}{2}} \end{aligned}$$
(19)

Notice that the Fortet linearization constraints (16)–(18) are now imposed in \(M_2\) for all \(i, j \in \mathcal {\hat{J}}\setminus \{1\}\).

2.2 Quadratic Cuts Used to Strengthen the MIP Models

In this subsection, we explain how we obtain quadratic cuts, which are then linearized to further strengthen the LP relaxations of the MIP models. By doing so, we intend to measure the impact of these cuts on the performance of the branch and cut algorithm of the Gurobi solver [4] when solving \(M_1\) and \(M_2\). We denote by \(M_1^{s}\) and \(M_2^{s}\) the strengthened versions of models \(M_1\) and \(M_2\), respectively. The set of linearized quadratic cuts we add in \(M_1^{s}\) are

$$\begin{aligned}&\sum _{j \in \mathcal {J}} z_{ij} = py_{i}, \quad \forall i \in \mathcal {J} \end{aligned}$$
(20)
$$\begin{aligned}&\sum _{\begin{array}{c} i,j \in \mathcal {J}\\ (i<j) \end{array}} z_{ij} = \frac{p(p-1)}{2} \end{aligned}$$
(21)
$$\begin{aligned}&y_i+y_j \le 1+z_{ij}, \quad \forall i,j \in \mathcal {J}, (i<j) \end{aligned}$$
(22)

The first cut (20) is obtained by multiplying constraint (3) by each \(y_i\), for all \(i \in \mathcal {J}\). Whilst the cardinality cut (21) is obtained by multiplying constraint (3) with each variable \(y_i\) for all \(i \in \mathcal {J}\). Then, we take the sum over all the resulting constraints and obtain the equality \(\sum _{i,j \in \mathcal {J}} y_iy_j = p^{2}\), which is equivalent to

$$\sum _{i,j \in \mathcal {J},(i \ne j)} y_iy_j = p(p-1)$$

and

$$\sum _{i,j \in \mathcal {J},(i < j)} z_{ij} = \frac{p(p-1)}{2}$$

Subsequently, the cuts in (22) are obtained from the quadratic valid inequalities \((1-y_i)(1-y_j)\ge 0\) for all \(i,j \in \mathcal {J},(i<j)\). Observe that each term in these inequalities is nonnegative since \(y_i\le 1\) for each \(i \in \mathcal {J}\). Finally, notice that the cuts (20)–(22) can be straightforwardly adapted for \(M_2\) while using the set \(\mathcal {\hat{J}}\setminus \{1\}\) instead of \(\mathcal {J}\).

3 Numerical Experiments

In this section, we present preliminary numerical results for all the proposed models. For this purpose, we implement a Python program using Gurobi solver [4]. In particular, we solve each quadratic model while setting the Gurobi option parameter Nonconvex to a value of 2. This option allows one to solve a non-convex quadratic problem with spatial branch and bound algorithms. We decided to use this option as it proved to be the most effective one in terms of CPU time required to solve the quadratic models. Whilst for the MIP and LP models, we use the Gurobi solver with default options. This implies solving the linear models with state-of-the-art branch and cut-based algorithms. The numerical experiments have been carried out on an Intel(R) 64 bits core (TM) with 3 GHz and 8G of RAM under Windows 10. So far, we generate eight instances with dimensions of \(n=\{50;60\}\) and \(m=\{200;250;300;350\}\), and each of them is solved for values of \(P=\{10;20\}\). We mention that this range of parameter values was arbitrarily chosen in order to ensure that hard instances were obtained. In a larger version of this paper, a wider range of parameter values will be considered. The input matrices \(C=C_{uj}\) and \(D=D_{ij}\) for all \(u \in \mathcal {I}\) and \(i,j \in \mathcal {J}\) are generated by computing the distances between users and facilities and between facilities themselves. Notice that matrix D is symmetric. The coordinates of each user and facility node are randomly drawn from the interval (0; 1).

In Table 1, we present preliminary numerical results obtained with models \(Q_1\) and \(M_1\). More precisely, in columns 1–4 we present the instance number, and the values of p, m, and n, respectively. Next, in columns 5–8 we report for \(Q_1\), the best objective function value obtained in at most 1h of CPU time, the number of branch and bound nodes, CPU time in seconds required to solve the model, and the MipGap parameter value of Gurobi solver, respectively. Gurobi computes this parameter by subtracting from the best incumbent solution the best lower bound obtained. Then, it divides this result by the incumbent solution again. Notice that this value is reported as a percentage. Also notice that if the Gurobi solver terminates with an optimal solution, then the MipGap parameter should be equal to zero. Subsequently, in columns 9–15 we report for \(M_1\), the best objective function value obtained in at most 1 h, the number of branch and bound nodes, CPU time in seconds, the optimal objective value of its LP relaxation, and CPU time in seconds required to solve it, and the gap and MipGap values, respectively. The gap is computed by \(\left[ \frac{Best-LP}{Best}\right] *100\).

Table 1. Numerical results obtained with \(Q_1\) and \(M_1\).
Full size table
Table 2. Numerical results obtained with \(Q_2\) and \(M_2\).
Full size table

In Table 2, we report numerical results for the models \(Q_2\) and \(M_2\). The column information of Table 2 is analogous to Table 1. Finally, in Table 3 we report preliminary numerical results for the linear models \(M_1^{s}\) and \(M_2^{s}\). Its legend is analogous as for the linear models reported in Tables 1 and 2 for \(M_1\) and \(M_2\), respectively.

Table 3. Numerical results obtained with \(M_1^{s}\) and \(M_2^{s}\).
Full size table

From Table 1, we first observe that both models \(Q_1\) and \(M_1\) allow obtaining the same objective function values except for the instance #8, for which we obtain a slightly smaller value with \(M_1\). Regarding the number of branch and bound nodes, we see that Gurobi reports a significantly less number of nodes for \(M_1\). The CPU times show that we can obtain the optimal solution of the problem for a larger number of instances with \(M_1\) in less than 1h. Next, we observe that the MipGap values reported for both models are close to zero. The latter indicates that the solutions reported are near-optimal. Notice that from these values, we can obtain tight lower bounds for the problem as well. Finally, we see that the LP relaxation of \(M_1\) is not tight when compared to the best objective function values and that the gaps obtained increase with p.

From Table 2, we observe similar trends for \(Q_2\) and \(M_2\). We notice that \(M_2\) significantly outperforms model \(Q_2\) in terms of the best objective function and CPU time values obtained. Indeed, we obtain the optimal solution to the problem with proven optimality for all tested instances. This cannot be achieved by any of the other proposed models reported in Tables 1 and 2. This achievement can also be observed by looking at the number of branch and bound nodes obtained, which are significantly lower for \(M_2\). Finally, we observe that the LP relaxation of \(M_2\) is not tight either. Similarly, from Table 3 we observe that \(M_2\) outperforms \(M_1\) in terms of all column information reported. In particular, we confirm that \(M_2\) allows obtaining the optimal solution of the problem for all the instances. Perhaps, one of the most interesting observations of Table 3 is that the LP bounds obtained with \(M_2^{s}\) are significantly higher than those reported in Tables 1 and 2, respectively. Ultimately, we observe that the impact of adding linearized quadratic cuts in \(M_2\) is not so strong in terms of CPU time values obtained. However, we see that for most of the instances, the number of branch and bound nodes decreases when these cuts are added to the models.

4 Conclusions

In this paper, we considered the problem of minimizing simultaneously the total connectivity cost of a set of users to a set of facility nodes and among facilities themselves. The problem is motivated by the potential development of future smart transportation and wireless network applications where interacting facilities will be required to be connected and nearly reachable. We proposed two mixed-integer quadratic programming models, which are further linearized. The first one is obtained as an extension of the classical p-Median formulation. Whereas the second one corresponds to an alternative set-covering model. Finally, we strengthen the linear models by imposing additional linearized quadratic cuts. So far, we solved hard instances with up to 60 facility nodes and 350 users. Our preliminary numerical results indicated that the linearized set-covering formulation outperforms all the other proposed models as it allows solving all the instances with proven optimality and in significantly less computational effort.

As future research, new models and algorithms should be investigated in order to tackle this hard combinatorial optimization problem. Complementarily, new cutting plane approaches should be proposed in conjunction with the new models. This would allow a complete validation of the proposal. Ultimately, the study problem in this paper should be adapted to more specific transportation and telecommunication network problems as part of future work.