# How to linearize a weighted maximum coverage problem?

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}

• What is nonlinear here? Apr 20 '20 at 21:39
• Sorry, actually the correct question should be: Is it possible that the binary variables above be modeled as continuous variables? Apr 20 '20 at 22:30
• Hi and welcome to ORSE. Could you please edit your question based on the comment that you posted? Apr 20 '20 at 23:23
• The max covering problem is well known to be NP hard, meaning a linear formulation would require an exponential number of variables/constraints
– Sune
Apr 21 '20 at 13:21
• @OguzToragay sure! Apr 21 '20 at 18:31

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)1 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.

• That's great. I'll test that and see if I can get close to 80%. Thank you. Apr 21 '20 at 19:17