3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

You easily see that:

  • if $y=0$, then $z=0$; and
  • if $y=1$, then $z=x$.
$\endgroup$
  • $\begingroup$ Awesome, thank you! If $x$ is unbounded, is there a way to do it, or is that impossible? $\endgroup$ – D.W. Mar 13 '16 at 19:36
  • $\begingroup$ 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. $\endgroup$ – Azzoubeir Mar 13 '16 at 19:50
  • $\begingroup$ OK. Makes sense. I guess the main remaining case is where $x \in [0,+\infty)$. $\endgroup$ – D.W. Mar 13 '16 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.