# Reformulate indicator function using mixed integer program

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

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$$.
• 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?