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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\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$.
Improve this answer
$\endgroup$
3
  • $\begingroup$ Awesome, thank you! If $x$ is unbounded, is there a way to do it, or is that impossible? $\endgroup$
    – D.W. ♦
    Mar 13, 2016 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$
    – Azz
    Mar 13, 2016 at 19:50
  • $\begingroup$ OK. Makes sense. I guess the main remaining case is where $x \in [0,+\infty)$. $\endgroup$
    – D.W. ♦
    Mar 13, 2016 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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