How to linearize a chain of if-then constraints?

Question

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 $

Answer 1

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

Answer 2

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.

Answer 3

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$