2
$\begingroup$

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}

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That's great. I'll test that and see if I can get close to 80%. Thank you. $\endgroup$
    – foliveira2
    Apr 21, 2020 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.