How to formulate "If statement with equality constraints" using big m?

Question

How to convert this one to a linear program:

if $x=1$ then $B=1$; otherwise, $B=0$.

If I use the Big M method: \begin{align}x&\ge1-M(1-B)\\x&\le1+M(1-B)\end{align}

A) with $B=1$: \begin{align}x&\ge1\\x&\le1\end{align} That is corresponding to $x=1$

B) with $B=0$: \begin{align}x&\ge1-M\\x&\le1+M\end{align} That is corresponding to any value of $x$ even $x=1$. How do I exclude $x=1$ when $B=0$?

If $x$ is continuous with constant bounds $-M \le x \le M$, see my answer here (take $b=1$, $L=-M$, and $U=M$): https://or.stackexchange.com/a/2632/500 — RobPratt, Nov 25 '22 at 18:46

Sutanu Majumdar · Answer 1 · 2022-11-26T03:39:49.093

0

I think the two constraints put in there, lead to the same thing, just change the sign of one of those and then add the two constraints, it will lead to $M \ge 0$. Assuming $x$ is continuous, then you need:
C1 = $B \ E \ [0,1] \ and \ z \le 0$: B is binary.
Choose U such that it's the upper bound for x
C2 = $Uz \le x$: z is <0 for x=99, z will remain <0 for x=-99 as U is larger than x and when x=1, z=0
C3 = $Uz+L(z-1) \ge (1-x)*(L-U)$: if x=1 z is forced to 0 due to C2, if x=99, z remains <0, if x=-99, z is again <0
C4 = $B \ge z+1$: z <0, B can be 0 but when z=0, B =1
and Choose $M \gt \lvert {x} \rvert+1$, $L$ is lower bound of $x$ and should be <0 and $U$ is upper bound of $x$ and >0

edited Nov 26 '22 at 03:39

answered Nov 25 '22 at 20:44

Sutanu Majumdar

3,461
1
2
11

x is continuous. Thanks for your trail of help, but that does not work. If x=0, then: C2 = M.B-M>=0: thus B=1 C3 = M.B-1<=M: thus, B is free.
To satisfy C2 and C3, B will be 1. Thus your suggestion does not work.
– Hussein Sharadga Nov 26 '22 at 01:09
Now? Does it solve? – Sutanu Majumdar Nov 26 '22 at 01:44
Sorry no let assume 0<=x<=10 C2: Uz<=x with x=1: 10z<=1 z<=0.1 and z<=0 does not mean z==0 – Hussein Sharadga Nov 26 '22 at 04:22
But look at c3, z=-0.1, would make it infeasible, so solver will choose to make it 0. – Sutanu Majumdar Nov 26 '22 at 04:54
I will double-check and let you know. Thank you. – Hussein Sharadga Nov 26 '22 at 04:59
For c3, rhs is (1-x)*(L-U). Sometimes I see (L-U) is appearing after the if statement, may b due to my mobile screen layout. – Sutanu Majumdar Nov 26 '22 at 05:04
Sorry, It does not work. I guess that I would go with the following by introducing more binary variables as suggested by @RobPratt: https://or.stackexchange.com/a/2632/500 If you have other suggestions please let me know! – Hussein Sharadga Nov 26 '22 at 07:00

score -1 · Answer 2 · answered Nov 25 '22 at 19:10

-1

if x and B both are binary then x+B>=2 should work. this contriant is satisfactory only under one condition that is both x and B should be 1. for every other condition the constraint will be voilated.

answered Nov 25 '22 at 19:10

Shahrukh Mohd

11

1

If $x$ and $B$ are both binary, then $x=B$ is instead the correct constraint. – RobPratt Nov 25 '22 at 20:26
That means the only solution is when x=1, but the optimal solution can be zero. By the way, the x variable is continuous – Hussein Sharadga Nov 26 '22 at 00:39

How to formulate "If statement with equality constraints" using big m?

2 Answers2