3
$\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$
  • $\begingroup$ What is nonlinear here? $\endgroup$ – RobPratt Apr 20 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$ – fsimoyama Apr 20 at 22:30
  • 1
    $\begingroup$ Hi and welcome to ORSE. Could you please edit your question based on the comment that you posted? $\endgroup$ – Oguz Toragay Apr 20 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 at 13:21
  • $\begingroup$ @OguzToragay sure! $\endgroup$ – fsimoyama Apr 21 at 18:31
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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ That's great. I'll test that and see if I can get close to 80%. Thank you. $\endgroup$ – fsimoyama Apr 21 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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