# Linearizing a disjunctive expression into MILP

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

• Your proposal cuts off the feasible solution $(w_1,w_2,x)=(1,1,a)$. Mar 4 at 12:23
• 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. Mar 4 at 13:02
• 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. Mar 4 at 13:34
• 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/… Mar 4 at 14:27

## 2 Answers

Because $$a, 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}

• 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?) Feb 21 at 14:13
• 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. Feb 21 at 14:26
• 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? Feb 22 at 10:22
• 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? Feb 22 at 10:25
• 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. Feb 22 at 18:47

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.