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:


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


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


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


$$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's gravatar image

accept rate: 0%

edited 08 Apr '16, 06:14

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

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%20Pratt's gravatar image

Rob Pratt
accept rate: 28%

edited 20 Mar '16, 14:56

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

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%20Pratt's gravatar image

Rob Pratt
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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 20 Mar '16, 08:49

Seen: 621 times

Last updated: 08 Apr '16, 06:14

OR-Exchange! Your site for questions, answers, and announcements about operations research.