1
$\begingroup$

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 $

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    May 31, 2023 at 13:31
  • 2
    $\begingroup$ If $\delta^d_{i,j}$ is a binary variable, then $\delta^d_{i,j} \le 1$ is always true. $\endgroup$
    – prubin
    May 31, 2023 at 15:33
  • $\begingroup$ 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 $\endgroup$
    – linkho
    Jun 3, 2023 at 17:38
  • 1
    $\begingroup$ Sorry for the confusion. I had misplaced the parentheses in the second one. I meant $(p \implies q) \implies r$. $\endgroup$
    – RobPratt
    Jun 3, 2023 at 18:56
  • $\begingroup$ Please edit your question to write the two desired implications separately. $\endgroup$
    – RobPratt
    Jun 3, 2023 at 19:00

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you very much for detialed explanation @RobPratt it cleared things up in my mind :) $\endgroup$
    – linkho
    Jun 5, 2023 at 16:32
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ thanks. But if $\delta =0$ then $x$ nust be less than N, but in here it become equal too $\endgroup$
    – linkho
    May 31, 2023 at 8:22
  • 1
    $\begingroup$ 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. $\endgroup$
    – A.Omidi
    May 31, 2023 at 8:31
  • $\begingroup$ In my first linear constraint if delta =0 then x<n. $\endgroup$
    – A.Omidi
    May 31, 2023 at 8:35
1
$\begingroup$

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$

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