# Maximise population coverage subject to budget constraint

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.

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

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.

• Thanks Macavity. Edited. How is it? – BCLC Mar 15 '16 at 6:08
• 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. – Macavity Mar 15 '16 at 6:10
• 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? – BCLC Mar 15 '16 at 11:31
• Using an $M$ is also a good way, though not needed here. Try out the Integer Programs and see how it works. – Macavity Mar 15 '16 at 11:43
• @BCLC Yes, your try 4 seems what I meant, and it works. – Macavity Mar 20 '16 at 18:31

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

• 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. – Kuifje Mar 17 '16 at 18:03
• 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 – BCLC Mar 17 '16 at 18:14
• 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? – Kuifje Mar 17 '16 at 18:25
• 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. – Kuifje Mar 18 '16 at 0:34
• yes indeed, for the same reasons. – Kuifje Mar 18 '16 at 14:30