# How to linearize a chain of if-then constraints?

How can I express the process of converting a series of if-then constraints into a linear form?

Let's assume that we have integer variable $$x_i$$, non-negative variables $$y_i^d$$, and binary variables $$\delta_{i,j}^d$$. Additionally, we assume that N and S are natural numbers, and A and B are subsets of all links $$(i,j) \in E$$, where A and B represent links that do not intersect.

The conditional statements:

If $$x_i \geq N$$ then The $$\delta_{i,j}^d = 1$$ or $$\delta_{i,j}^d = 0$$. but if $$\delta_{i,j}^d = 1$$ I want to ensure that $$y_i^d \leq y_j^d - S \quad \forall (i,j) \in A$$

But If $$x_i < N$$ I want to ensure that $$\delta_{i,j}^d=0 \quad \forall (i,j) \in A$$ but they could take value fron set$$B$$. in other words, $$\delta_{i,j}^d =0$$ or $$\delta_{i,j}^d =1 \quad \forall (i,j)\in B$$ And if this latter happen $$y_i^d \leq y_j^d - N \cdot S \quad \forall (i,j)\in B$$

• Be careful: $$p \implies q \implies r,$$ $$p \implies (q \implies r),$$ and $$(p \implies q) \land (q \implies r)$$ mean three different things. I think you meant the last one. May 31 at 13:31
• If $\delta^d_{i,j}$ is a binary variable, then $\delta^d_{i,j} \le 1$ is always true.
– prubin
May 31 at 15:33
• Thanks very much for the heads up @RobPratt. I've been thinking why the first two are diffrenet? And Yes, For $A$ I want to ensure if $x>N$ then $\delta$ could be one and if ever $\delta$ take a value of one then $y$ to be calculated like that Jun 3 at 17:38
• Sorry for the confusion. I had misplaced the parentheses in the second one. I meant $(p \implies q) \implies r$. Jun 3 at 18:56
• Please edit your question to write the two desired implications separately. Jun 3 at 19:00

For $$(i,j)\in A$$, you want to enforce $$\delta_{i,j}^d = 1 \implies y_i^d \le y_j^d - S \tag1\label1$$ and $$x_i < N \implies \delta_{i,j}^d=0 \tag2\label2$$ For $$(i,j)\in B$$, you want to enforce $$\delta_{i,j}^d =1 \implies y_i^d \le y_j^d - N \cdot S \tag3\label3$$

To enforce \eqref{1}, use big-M: $$y_i^d - y_j^d + S \le M(1-\delta_{i,j}^d) \quad \text{for (i,j)\in A}$$ To enforce \eqref{2}, first rewrite as its contrapositive: $$\delta_{i,j}^d=1 \implies x_i \ge N$$ and then use big-M: $$N - x_i \le M(1-\delta_{i,j}^d) \quad \text{for (i,j)\in A}$$ To enforce \eqref{3}, use big-M: $$y_i^d - y_j^d + N\cdot S \le M(1-\delta_{i,j}^d) \quad \text{for (i,j)\in B}$$ Note that the values of $$M$$ are different in these three cases. In each case, $$M$$ should be a (small) constant upper bound on the LHS when $$\delta_{ij}^d=0$$.

• Thank you very much for detialed explanation @RobPratt it cleared things up in my mind :) Jun 5 at 16:32

If the binary variable $$\delta_{i,j}^d$$ is defined to linearize, Your first clause can be converted as:

$$Iff \quad ((x_i \geq N) \implies \delta_{i,j}^d = 1)) \quad \implies ((\delta_{i,j}^d = 1) \implies y_i^d \leq y_j^d - S)$$ is equal to:

$$Iff \quad ((\delta_{i,j}^d = 0) \implies x_i \leq N) \quad \implies ((\delta_{i,j}^d = 1) \implies y_i^d \leq y_j^d - S)$$

It yields the following linear constraints:

$$x_{i} \leq N + M_{1}\delta_{i,j}^d \quad (1)$$ $$y_{i} - y_{j} + S\leq M_{2}(1-\delta_{i,j}^d) \quad (2)$$

For the second clause, the procedure is the same.

• thanks. But if $\delta =0$ then $x$ nust be less than N, but in here it become equal too May 31 at 8:22
• I am not sure understanding your comment well, but in the first, you want x>N if delata=1 which is equal to if delta=0 then x<N. In the second, the condition is reversed. In that you want x<N if delta = 0 which is equal to if delta=1 then x>N. May 31 at 8:31
• In my first linear constraint if delta =0 then x<n. May 31 at 8:35

Going by @Omidi answer, constr (1) solves your problem for $$N \lt x$$ but to achieve $$\delta =1$$ for $$x=N$$ you can try\

$$N - M\alpha - M\delta \le x \le N + M\delta - \epsilon\alpha$$
$$\delta + \alpha \le 1$$
where $$0 \le \epsilon \lt \min (\vert x-N \vert)$$
This makes $$\delta$$ free for $$x\lt N$$

So $$x\lt N$$ define another binary $$\beta$$ as
$$N \le x + M\beta$$
$$\epsilon\beta -M(1-\beta) \le N-x$$