Integer programming problem

Question

I have the following exercise:

Stockco is considering four investments. Investment 1 will yield a net present value (NPV) of \$16,000; investment 2, an NPV of \$22,000; investment 3, an NPV of \$12,000; and investment 4, an NPV of \$8,000. Each investment requires a certain cash overflow at the present time: investment 1, \$5,000; investment 2, \$7,000; investment 3, \$4,000; and investment 4, \$3,000. Currently, \$14,000 is available for investment. Formulate an IP whose solution will tell Stockco how to maximize the NPV obtained from investments 1-4.

As in LP formulations, we begin by defining a variable for each decision that Stockco must make. This leads us to define a 0-1 variable: $$x_j(j=1,2,3,4)=\begin{cases}1\quad\text{if investment}\,j\,\text{is made}\\0\quad\text{otherwise}.\end{cases}$$

Suppose we add the following restriction to Example 1 (Stockco):

If investments 2 and 3 are chosen, then investment 4 must be chosen. What constraints would be added to the formulation given in the text?

The solution is as given below:

Condition 2: If investments 2 and 3 are chosen, then investment 4 must be chosen. This condition is obtained by the constraint $x_2+x_3-2x_4\le0$. If both $x_2,x_3=1$, then $x_4$ must be $1$. Otherwise $x_4$ may be zero. Hence the condition is satisfied.

Hence the following IP is formulated. \begin{alignat}2\max&\quad16x_1+22x_2+12x_3+8x_4\\\text{s.t.}&\quad5x_1+7x_2+4x_3+3x_4&\le14\\&\quad x_2+x_3-2x_4&\le0\\&\quad x_1,x_2,x_3,x_4&\ge0\end{alignat} My question: Is the solution correct? It seems incorrect since it's a "$x_2$ or $x_3$ are chosen" statement, not a "$x_2$ and $x_3$ are chosen" statement. i.e it satisfies for one of them to be chosen for the inequality to be true.

Answer 1

The given constraint is a weak linearization of $(x_2 \lor x_3)\implies x_4$, which can be rewritten in conjunctive normal form as $(\neg x_2 \lor x_4) \land (\neg x_3 \lor x_4)$, yielding the tighter linearization $x_2 \le x_4 \land x_3 \le x_4$.

The wording of the problem seems to instead mean $(x_2 \land x_3)\implies x_4$, which can be rewritten in conjunctive normal form as $\neg x_2 \lor \neg x_3 \lor x_4$, yielding the linearization $x_2 +x_3 -1\le x_4$.

Answer 2

With $x_2 + x_3 \le 2x_4$, you see that $x_4$ can be $0$ or $1$ only if both $x_2$ and $x_3$ are $0$. In any other case, $x_4=1$. If you want to enforce a constraint that "$x_4=1$ if $x_2$ and $x_3$ are both $1$", then you can have $x_4 \ge x_2 + x_3 -1$.