How to transform a nonlinear constraint to linear constraint using big M?

Question

Given a nonlinear constraint $$xy=0$$ where $x$ is a continuous variable and $y$ is a binary variable.

Question: Using the Big-M method, how do I get to change the constraint above to a linear constraint below: $$x \leq M(1-y)?$$ Probably by showing a theorem.

What I know: I know that $M$ is probably a variable to bound the continuous variable $x$ so that it applies $0 \leq x \leq M$.

Thank you for the help.

Answer 1

Because $y$ is a binary variable, you just need to check the two cases.

• If $y=0$, then $xy=0$, as desired, and the linear constraint reduces to $x \le M$, which is redundant.
• If $y=1$, you want to enforce $x=0$ so that $xy=0$. Because $x \ge 0$, it is enough to enforce $y = 1 \implies x \le 0$. The big-M constraint $x \le M(1-y)$ does exactly that.

More generally, to enforce $y=1 \implies f(x) \le b$, impose $f(x) - b \le M(1-y)$, where $M$ is an upper bound on $f(x) - b$ when $y=0$.