3
$\begingroup$

I'm trying to formulate the following logic:
If $y_i =1$, then $c_i \leq x_i$
If $y_i =0$, then $c_i \leq 0$
Where $y_i$, $c_i$, and $x_i$ are decision variables.

The easy way would be to write: $$c_i \leq x_i y_i$$ But that is a quadratic formulation. I was wondering if there is a way to write the constraint as a linear one.

Consider that $c_i$, $x_i$ $\geq 0$ and $y_i \in \{0,1\}$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Something like: $$\begin{align} & c_i \le x_i + M(1-y_i)\\ & c_i \le My_i \end{align}$$ $M$ can be interpreted as an upperbound on $c_i$. If you don't like the big-$M$'s, consider using indicator constraints.

See the comments below for some improvements on this!

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Erwin knows this, but a best practice is to use $M_i$ (a possibly different value for each $c_i$). $\endgroup$
    – RobPratt
    Commented Jan 12, 2022 at 19:59
  • $\begingroup$ And may be even a different $M_i$ for the two constraints (if we know something about the difference between $c_i$ and $x_i$). $\endgroup$
    – Erwin Kalvelagen
    Commented Jan 12, 2022 at 20:15
  • 4
    $\begingroup$ Since $x_i\ge 0$, the first constraint can be simplified to $c_i \le x_i$. $\endgroup$
    – prubin ♦
    Commented Jan 12, 2022 at 20:22
  • $\begingroup$ Great, I missed that. $\endgroup$
    – Erwin Kalvelagen
    Commented Jan 12, 2022 at 20:38
  • $\begingroup$ Indeed, Paul's improvement arises from interpreting the first $M$ as a (small) upper bound on $c_i-x_i$ when $y_i=0$. Because $c_i=0$ in that case, we have $c_i-x_i = -x_i \le 0$, so take $M=0$. $\endgroup$
    – RobPratt
    Commented Jan 12, 2022 at 21:22

Your Answer

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