# Maximise population coverage subject to budget constraint

 0 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. asked 20 Mar '16, 08:49 BCLC 8●3●12 accept rate: 0% Your problem is a variant of the (relatively) famous maximum covering location problem. You can read the original paper here. (21 Mar '16, 03:23) Sune

 2 OK, try 2 is still wrong but at least uses existing variables. Yes, $$c_1 \le x_1 + x_3$$ correctly models the implication, and your try 4 looks good. By the way, you can derive the linear constraint automatically by rewriting the implication in conjunctive normal form: \begin{align} c_1 &\implies (x_1 \vee x_3) \\ \neg c_1 &\bigvee (x_1 \vee x_3) \\ \neg c_1 &\vee x_1 \vee x_3 \\ (1 - c_1) &+ x_1 + x_3 \ge 1 \\ c_1 &\le x_1 + x_3 \end{align} answered 20 Mar '16, 14:36 Rob Pratt 1.2k●2●6 accept rate: 28% Nice technique. Thanks Rob Pratt ^-^ (24 Mar '16, 14:13) BCLC I think you forgot some constraints? I edited my post. How is it please? Also, from where did you get the $$\ge 1$$ in the penultimate line in your answer? (26 Mar '16, 19:50) BCLC The basic relationship is that $$\bigvee_i z_i$$ corresponds to $$\sum_i z_i \ge 1$$. A disjunction is true iff at least one of its operands is true. A sum of binary variables is at least 1 iff at least one of the summands is 1. You can omit your $$c_j \ge t_i$$ constraints because they will naturally be satisfied due to the maximization objective. (26 Mar '16, 23:21) Rob Pratt
 1 Your try 2 uses variables that don't exist. Hint: for community 1, you want to model the logical implication $$c_1 \implies (x_1 \vee x_3)$$. answered 20 Mar '16, 13:44 Rob Pratt 1.2k●2●6 accept rate: 28% Oh thanks Rob Pratt! Edited try 2. Um, $$c_1 \le x_1 + x_3$$ ? If $c_1$ is covered, then it is done so by $x_1$ or $x_3$? (20 Mar '16, 13:55) BCLC
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: