# Express product in ILP

Suppose I have a mixed integer-linear program (MILP) with variables $x,y,z$, where $y$ is a 0-or-1 variable, and I want to impose the constraint $z=xy$. This is not expressible in a MILP directly. Is there a way to express this using linear inequalities, by adding some new variables (possibly variables restricted to integers)?

To put it another way: I want to express the constraint $(z=0 \land y=0) \lor (z=x \land y=1)$, in a situation where I already know $y$ is constrained to be either 0 or 1.

It depends on $x$ being bounded or not.
Suppose that $x$ is bounded as $x\in[0,x_{\mathrm{max}}]$. Then, the constraint $z=xy$ can be written as: $$\begin{cases} z\leq x_{\mathrm{max}} y,\\ z\leq x,\\ z\geq x-(1-y)x_{\mathrm{max}},\\ z\geq 0. \end{cases}$$
• if $y=0$, then $z=0$; and
• if $y=1$, then $z=x$.
• Awesome, thank you! If $x$ is unbounded, is there a way to do it, or is that impossible? – D.W. Mar 13 '16 at 19:36
• You are welcome. I know that you can do it for $x\in[x_{\mathrm{min}},x_{\mathrm{max}}]$. If $x\in\mathbb{R}$, I guess you can write $x$ as $x=x_1-x_2$ where $x_1\geq0$ and $x_2\geq0$. Maybe, you can restrict $x_1$ and $x_2$ to be less than $M_1$ and $M_2$, respectively, where $M_1$ and $M_2$ are big numbers. – Azzoubeir Mar 13 '16 at 19:50
• OK. Makes sense. I guess the main remaining case is where $x \in [0,+\infty)$. – D.W. Mar 13 '16 at 19:51