How to linearize a weighted maximum coverage problem?

Question

Is it possible that the binary variables below be modeled as continuous variables?

\begin{alignat}2\max&\quad\sum _{{e\in E}}w(e_{j})\cdot y_{j}\\\text{s.t.}&\quad\sum {x_{i}}\leq k,\quad&(\text{no more than}\,\,k\,\,\text{sets are selected})\\&\quad{\sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}},\quad&(\text{if}\,\,y_{j}>0\,\,\text{then at least one set}\,\,e_{j}\in S_{i}\,\,\text{is selected})\\&\quad{y_{j}\in \{0,1\}},\quad&(\text{if}\,\,y_{j}=1\,\,\text{then}\,\,e_{j}\,\,\text{is covered})\\&\quad{x_{i}\in \{0,1\}},\quad&(\text{if}\,\,x_{i}=1\,\,\text{then}\,\,S_{i}\,\,\text{is selected for the cover})\end{alignat}

Answer 1

I think there is no continuous form of the maximal covering location problem (MCLP) with a guarantee of providing the same optimal solution as the integer program. However, in addition to the formulation OP presented, Church & ReVelle (1974)¹ proposed a second formulation for the problem in their breakthrough paper, that is as follows:

\begin{alignat}4 \min &\quad z = \sum_{{j\in J}}w_j\cdot \bar y_{j}\\\text{s.t.}&\quad \sum_{i \in N_j} {x_{i}} + \bar y_{j} \geq 1, \qquad \forall j \in J;\tag1\\&\quad \sum_{i \in I} x_{i} = k; \tag2\\&\quad {x_{i} \in \{0,1\}}, \qquad \forall i \in I;\tag3\\&\quad {\bar y_{j} \in \{0,1\}}, \qquad \forall j \in J. \tag4\end{alignat}

and stated that this problem can be solved with continuous variables where both $x_{i}$ and $\bar y_{j}$ are defined as non-negative. That way, in 80% of the cases the optimal solution of the linear program was equal to the zero-one solution in their computations.

P.S. In this formulation $N_j = \{i \in I | d_{ij} \leq S\}$, and $\bar y_j = 1 - y_j$

_References:

_{[1] Church, Richard, and Charles ReVelle. "The maximal covering location problem." Papers of the regional science association. Vol. 32. No. 1. Springer-Verlag, 1974.}