# Integer programming problem

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.

• In future questions, could you please type the problem/solutions out instead of posting images? This makes it easier for searching and also for those who want to use certain phrases/equations in the question as part of their answer. – TheSimpliFire Dec 28 '19 at 8:05

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