Maximise population coverage subject to budget constraint

Question

---

---

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$$

2. 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$$

3. 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.

Answer 1

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.

Answer 2

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 $$