Question 26: In the Uncapacitated Facility Location (UCFL) problem, w…

In the Uncapacitated Facility Location (UCFL) problem, we are given $(\mathcal{F} \uplus \mathcal{D}, d)$ as well auxiliary information which specifies the cost $f_i$ of opening a facility at location $i \in \mathcal{F}$. The goal is to open a subset of facilities in $\mathcal{F}$ to minimize the sum of the cost of the opened facilities and the total distance traveled by the clients to their nearest open facility.

In other words we want to solve

$\min_{\mathcal{F}' \subseteq \mathcal{F}} \left( \sum_{i \in \mathcal{F}} f_i + \sum_{j \in \mathcal{D}} d\left(j, \mathcal{F}'\right) \right).$

Consider the following LP formulation for the problem. We use a variable $y_i$ for $i \in \mathcal{F}$ to indicate whether $i$ is opened or not. We use a variable $x_{i,j}$ to indicate whether $j$ is assigned to $i$. One set of constraints are natural here: each client has to be assigned/connected to a facility. The other constraint requires that $j$ is assigned to $i$ only if $i$ is open.

Consider the LP below:

$\begin{aligned} &\min \sum_{i \in \mathcal{F}} f_i y_i + \sum_{j \in \mathcal{D}} \sum_{i \in \mathcal{F}} d(i,j) x_{i,j} \\ &\qquad \sum_i x_{i,j} = Q \quad \forall j \in \mathcal{D} \\ &\qquad x_{i,j} \leqslant y_i \quad i \in \mathcal{F}, j \in \mathcal{D} \\ &\qquad x, y \geqslant 0 \end{aligned}$

What is the correct value of Q?