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

$\endgroup$
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!

$\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
    Jan 12 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$ Jan 12 at 20:15
  • 4
    $\begingroup$ Since $x_i\ge 0$, the first constraint can be simplified to $c_i \le x_i$. $\endgroup$
    – prubin
    Jan 12 at 20:22
  • $\begingroup$ Great, I missed that. $\endgroup$ Jan 12 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
    Jan 12 at 21:22

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.