2
$\begingroup$

I want to linearize the following disjunctive form.

$$\left[\begin{gathered}w_{1}\\x \geq a\end{gathered}\right] \vee \left[\begin{gathered}w_{2}\\x \geq b\end{gathered}\right]$$

where $w_1$ and $w_2$ are binary and $x$ is a free variable $\in \{ -2, \cdots, 10\}$ and $\{ -2 \lt a \lt b \lt 10 \}$. I think one possible way is as follows:

$$\left[\begin{gathered}(w_{1}=1) \land (x \geq a) \end{gathered}\right] \vee \left[\begin{gathered}(w_{2}=1) \land (x \geq b)\end{gathered}\right]$$

Then:

$$(w_{1} \lor w_{2}) \bigwedge (w_{1} \implies x \geq a) \bigwedge (w_{2} \implies x \geq b)$$

I would like to know if, is there a way to linearize such a disjunctive form by introducing the new auxiliary variable $z$ for each disjunct? (Also, the answer by Rob is a perfect one).

$\endgroup$
4
  • $\begingroup$ Your proposal cuts off the feasible solution $(w_1,w_2,x)=(1,1,a)$. $\endgroup$
    – RobPratt
    Commented Mar 4, 2023 at 12:23
  • $\begingroup$ Dear Rob, this GDP is actually a part of the big GDP model and the final solution of the linearizing form is the same as the original one. $\endgroup$
    – A.Omidi
    Commented Mar 4, 2023 at 13:02
  • $\begingroup$ Your proposal does not cut off all feasible solutions, but it does cut off some of them, so you were a bit lucky that it didn’t cut off all optimal solutions. $\endgroup$
    – RobPratt
    Commented Mar 4, 2023 at 13:34
  • $\begingroup$ I would prefer to communicate through StackExchange so others can contribute to and benefit from the discussion. I created a room here: chat.stackexchange.com/rooms/144364/… $\endgroup$
    – RobPratt
    Commented Mar 4, 2023 at 14:27

2 Answers 2

5
$\begingroup$

Because $a<b$, the lower bound $x \ge a$ is valid for both parts. So linearize the following: $$ a\le x \le 10\\ z_1 \lor z_2 \\ z_1 \implies w_1 \\ z_2 \implies w_2 \\ z_2 \implies x\ge b $$ The resulting linear constraints are: \begin{align} z_1 + z_2 &\ge 1 \\ z_1 &\le w_1 \\ z_2 &\le w_2 \\ a + (b-a)z_2 \le x &\le 10 \end{align}


If the disjunction is instead intended to be exclusive, you can omit the $z_i$ variables and impose: \begin{align} w_1 + w_2 &= 1 \\ a + (b-a)w_2 \le x &\le 10 \end{align}

$\endgroup$
5
  • $\begingroup$ Many thanks, Dr. Pratt. It was really helpful. May I have also your insight about my last expression? (Is what I think correct or needs some tweaks?) $\endgroup$
    – A.Omidi
    Commented Feb 21, 2023 at 14:13
  • 2
    $\begingroup$ Your first clause is correct, but the other two are not. I recommend writing out all $2\times2\times13$ cases for $(w_1,w_2,x)$ to help see what's going on. $\endgroup$
    – RobPratt
    Commented Feb 21, 2023 at 14:26
  • $\begingroup$ Sorry for the late and thanks for updating the answer. Would you say please, what you pointed out in writing the cases, back to the original expression or the last line? $\endgroup$
    – A.Omidi
    Commented Feb 22, 2023 at 10:22
  • $\begingroup$ Also, can I write the last expression as $(z_{1} \lor z_{2}) \bigwedge (z_{1} \implies w_{1}) \bigwedge (z_{2} \implies w_{2})$? And then adding its corresponding linearization for the second and third clauses? $\endgroup$
    – A.Omidi
    Commented Feb 22, 2023 at 10:25
  • $\begingroup$ In your question, your second disjunction is not equivalent to the original, and checking cases would reveal that. For example, $(w_1,w_2,x)=(0,0,0)$ satisfies the second but not the original. $\endgroup$
    – RobPratt
    Commented Feb 22, 2023 at 18:47
0
$\begingroup$

From the modeling language point of view, the above disjunctive form can be written by CPLEX in the following form:

  c1: (y1==1 && x>=2) || (y2==1 && x>=3);
  c2: (y3==1 && x<=8) || (y4==1 && x==2.5);

or

  c1: (y1==1 || y2==1);
  c2: (y3==1 || y4==1);

and adding appropriate linearization constraints.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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