What if the 'or' is exclusive instead of inclusive?

261 Views Asked by At

The context is an integer programming problem on choosing projects to maximise profit.

I think (b) i. changes if 'either project 1 or project 3' means 'project 1 xor project 3' rather than 'project 1 or project 3'


enter image description here


What I tried:

Let $x_i =$

$1$, if project i is selected and $0$, otherwise.

and

$c_{ij}$ be the expenditure in project i in year j

Obj func: Max

$$z = r \cdot x - \sum_{i} x_ic_{i1} - \sum_{i} x_ic_{i2} - \sum_{i} x_ic_{i3}$$

where

$r_i$ is the return of project i

$$r' = [10, 40, 20, 15, 30]$$

$$x' = [x_1, x_2, x_3,x_4, x_5]$$

s.t.

$$\sum_{i} x_{i}c_{i1} \le 25$$

$$\sum_{i} x_{i}c_{i2} \le 25$$

$$\sum_{i} x_{i}c_{i3} \le 25$$


bii

$$x_2 + x_4 \le 1$$


bi

if either-or means or (inclusive or):

$$x_4 \ge x_1, x_4 \ge x_3$$

if either-or means xor (exclusive or):

$$x_4 \ge x_1 + x_3 - y$$

where $y=2$ if $x_1 = x_3 = 1$ and $0$ otherwise.


Is that right?


From Chapter 3 here.

2

There are 2 best solutions below

0
On BEST ANSWER

For inclusive or:

$$x_4 \ge x_1 \ \text{and} \ x_4 \ge x_3$$

For exclusive or:

$$x_3 + x_4 \ge x_1 \ \text{and} \ x_1 + x_4 \ge x_3$$


Proofs based on this:

For inclusive or:

$$(x_1 \bigvee x_3) \rightarrow x_4$$

$$\iff \neg (x_1 \bigvee x_3) \vee x_4$$

$$\iff (\neg x_1 \bigwedge \neg x_3) \vee x_4$$

$$\iff (\neg x_1 \vee x_4) \bigwedge (\neg x_3 \vee x_4) $$

$$\iff (1-x_1) + x_4 \ge 1 \ \text{and} \ (1-x_3) + x_4 \ge 1$$

$$\iff x_4 \ge x_1 \ \text{and} \ x_4 \ge x_3$$

For exclusive or:

$$(x_1 \bigvee x_3) \bigwedge \neg (x_1 \bigwedge x_3) \rightarrow x_4$$

$$\iff (x_1 \bigwedge \neg x_3) \bigvee (x_3 \bigwedge \neg x_1 ) \rightarrow x_4$$

$$\vdots$$

$$(\neg x_1 \bigvee x_3 \bigvee x_4) \bigwedge (\neg x_3 \bigvee x_1 \bigvee x_4)$$

$$(1 - x_1) + x_3 + x_4 \ge 1 \ \text{and} \ (1 - x_3) + x_1 + x_4 \ge 1$$

$$x_3 + x_4 \ge x_1 \ \text{and} \ x_1 + x_4 \ge x_3$$

1
On

As mentioned in the comments English is ambiguous. However, the standard has evolved that "or" always means inclusive or. It never means exclusive or.

Again, this is a convention of English language that's widely but not universally used, but is always my first assumption.