5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – TheSimpliFire Dec 28 '19 at 8:05
9
$\begingroup$

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

| improve this answer | |
$\endgroup$
7
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think you meant if instead of only if (the converse of if) in the last sentence. $\endgroup$ – RobPratt Dec 27 '19 at 21:52
  • $\begingroup$ True, corrected it. $\endgroup$ – EhsanK Dec 27 '19 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.