3

I have to minimize $c^Tx$ subject to $Ax = b$, $x_iw_i = 0$ for all $i$, with $x$ non negative continuous and $w$ binary. What model should I use to solve this problem?

Kuifje
  • 13,324
  • 1
  • 23
  • 56
fischer justin
  • 31
  • 1
  • https://or.stackexchange.com/questions/39/how-to-linearize-the-product-of-a-binary-and-a-non-negative-continuous-variable – Kuifje Jul 07 '23 at 11:08
  • @Kuifje That reformulation is correct but overkill for this special case where you want the product to be $0$. In particular, no new variable is needed, – RobPratt Jul 07 '23 at 12:59
  • yes indeed, I agree. Shall I remove the comment to avoid confusion? – Kuifje Jul 07 '23 at 13:43
  • Still useful to have the link for reference. – RobPratt Jul 07 '23 at 14:12

1 Answers1

4

Equivalently, you want to enforce $$w_i=1\implies x_i\le 0.$$ You can either use an indicator constraint to express this directly or use the following big-M constraint: $$x_i \le M_i(1-w_i),$$ where $M_i$ is a (small) constant upper bound on $x_i$.

RobPratt
  • 32,006
  • 1
  • 44
  • 84