-1
$\begingroup$

enter image description here


enter image description here


Let $t_i =$

$1$ if transmitter i is to be constructed

and $0$ otherwise,

$c_j =$

$1$ if community j is covered

and $0$ otherwise.

Obj func:

Max

$$z = [10, 15, ..., 10] \cdot c$$

s.t.

  1. the budget constraint

$$[3.6, 2.3, ..., 3.10] \cdot t \le 15$$

  1. If community $j$ is covered, it is done so by at least one constructed transmitter $i$:

eg if $c_1$ is covered, then $t_1$ or $t_3$ is constructed:

$$c_1 \to (t_1 \bigvee t_3)$$

$$\iff \neg c_1 \bigvee (t_1 \bigvee t_3)$$

$$\iff 1 - c_1 + t_1 + t_3 \ge 1$$

$$\iff c_1 \le t_1 + t_3$$

Similarly, we have:

$$c_2 \le t_1 + t_2$$

$$\vdots$$

$$c_{15} \le t_7$$

  1. If a transmitter $i$ is constructed, at least one community $j$ is covered:

eg if $t_1$ is constructed, then $c_1$ and $c_2$ are covered:

$$t_1 \to (c_1 \bigwedge c_2)$$

$$\iff \neg t_1 \bigvee (c_1 \bigwedge c_2)$$

$$\iff (\neg t_1 \bigvee c_1) \bigwedge (\neg t_1 \bigvee c_2)$$

$$\iff 1 - t_1 + c_1 \ge 1 \ \text{and} \ 1 - t_1 + c_2 \ge 1$$

$$\iff c_1 \ge t_1 \ \text{and} \ c_2 \ge t_1$$

Similarly, we have:

$$c_2, c_3, c_5 \ge t_2$$

$$c_1, c_7, c_9, c_{10} \ge t_3$$

$$\vdots$$

$$c_{12}, c_{13}, c_{14}, c_{15} \ge t_7$$


Is that right?


From Chapter 3 here.

$\endgroup$
  • $\begingroup$ Note if you choose transmitters $1, 2$, then there is overlap of communities, and your function will double count the population of community $2$. $\endgroup$ – Macavity Mar 15 '16 at 5:05
  • $\begingroup$ @Macavity Oh thanks. What to do then? $z'=z-y \cdot x$ where $y_i$ corrects for double or triple counting? $\endgroup$ – BCLC Mar 15 '16 at 5:10
  • $\begingroup$ @Macavity I think Kuifje found away around the double count. Do you agree? $\endgroup$ – BCLC Mar 17 '16 at 17:54
1
$\begingroup$

Here is a way to get the constraints right. Define $x_i$ exactly as you have done. Define $p_i$ to be an indicator $1/0$ depending on whether community $i$ has been covered or not.

The budget constraint remains as you have set, and the objective function is now of form $\max z = 10p_1+15p_2 + \cdots + 10p_{15}$

Now how do we ensure that $p_i$ is set correctly, for any given choice of $\{x_i\}$? One way is to note that the objective function gives positive weight to $p_i$, so define a constraint for each population based on transmitters which could cover it - e.g. for the first one : $p_1 \le x_1+x_3$, for the second $p_2 \le x_1 + x_2$ etc. This will force the population indicator to turn $0$ if none of the relevant transmitters are selected.

$\endgroup$
  • $\begingroup$ Thanks Macavity. Edited. How is it? $\endgroup$ – BCLC Mar 15 '16 at 6:08
  • $\begingroup$ Your $p_i$ needs to be replaced by $c_i$ in the objective function and $x_i$ has no role to play in the objective. $\endgroup$ – Macavity Mar 15 '16 at 6:10
  • $\begingroup$ Thanks. We answered in class, and we sort of got different answers. Prof is still going to think about it. How do you find sol? $\endgroup$ – BCLC Mar 15 '16 at 11:31
  • $\begingroup$ Using an $M$ is also a good way, though not needed here. Try out the Integer Programs and see how it works. $\endgroup$ – Macavity Mar 15 '16 at 11:43
  • 1
    $\begingroup$ @BCLC Yes, your try 4 seems what I meant, and it works. $\endgroup$ – Macavity Mar 20 '16 at 18:31
1
+50
$\begingroup$

This is a classical set covering problem.

Let $y_i$ be a binary variable that equals $1$ if and only if transmitter $i=1,\cdots,7$ is built, and $x_j$ another binary that equals $1$ if community $j$ is covered. Let $p_j$ be the population of community $j=1,\cdots,15$.

You want to maximize the total coverage: $$ \mbox{Maximize }Z=\sum_{j=1 }^{15}p_jx_j $$ subject to budget constraints: $$ \sum_{i=1}^7c_iy_i\le 15 \\ $$ To link the variables, proceed like Macavity suggests: $$ x_j\le \sum_{i\;|\;i \;covers\; j}y_i\quad \forall j=1,\cdots,15\\ y_i,x_j\in \{0,1\}\quad \forall i=1,\cdots,7\;\forall j=1,\cdots,15 $$

$\endgroup$
  • 1
    $\begingroup$ Sorry I was editing while you asked the question. Variables $x_j$ will make sure there is no double counting, and are activated as soon as one of the variables $y_i\; |\;i$ covers $j$ is. $\endgroup$ – Kuifje Mar 17 '16 at 18:03
  • $\begingroup$ No apologies needed. I'm the one asking a favour. It's really 'Try 2' and not 'Try 1' ? My prof seems to disagree with Macavity $\endgroup$ – BCLC Mar 17 '16 at 18:14
  • $\begingroup$ What do you mean by 'Try 1' and 'Try 2'? I think Macavity is right. He basically explained the nature of my second constraint. What specific point does your professor disagree with? $\endgroup$ – Kuifje Mar 17 '16 at 18:25
  • 1
    $\begingroup$ I disagree with "Try1". Try 1 (first equation) implies that if communities $1$ and $2$ are covered, than transmitter $1$ is built. This is not necessarily true, as they can be covered by transmitters $3$ and $2$ for example. It is the other way around: if community $1$ is covered, than at least one transmitter among those that cover the community must be built. $\endgroup$ – Kuifje Mar 18 '16 at 0:34
  • 1
    $\begingroup$ yes indeed, for the same reasons. $\endgroup$ – Kuifje Mar 18 '16 at 14:30

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.