Consider the following constraint: $$ \sum_i I(a_i x \leq b) \leq m. $$ Can we reformulate this constraint using big-M constraint?

A similar question can be found in Involving indicator function as a constraint in a LP problem. The difference is we have the sum of indicator functions less than $m$ instead of greater than $m$.


1 Answer 1


Let $\epsilon>0$ be a small constant tolerance, introduce binary variables $y_i$ to represent the indicator, and impose linear constraints \begin{align} \sum_i y_i &\le m \tag1 \\ b - a_i x + \epsilon &\le M_i y_i &&\text{for all $i$} \tag2 \end{align} Constraint $(1)$ forces at most $m$ of the $y_i$ variables to be $1$. Big-M constraint $(2)$ enforces $y_i = 0 \implies a_i x > b$, the contrapositive of $a_i x \le b \implies y_i = 1$. If $a_i$, $x$, and $b$ are all integer, you can take $\epsilon=1$.

  • $\begingroup$ Thanks! BTW, The constraint should be $b-a_i x+\epsilon \leq M_i y_i$? And the reformulation is actually equivalent to $\sum_i I(a_i x < b+\epsilon) \leq m$, am I correct? $\endgroup$
    – Kaka
    Apr 24, 2021 at 4:09
  • $\begingroup$ Yes and yes. I corrected the sign. $\endgroup$
    – RobPratt
    Apr 24, 2021 at 4:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .