Involving indicator function as a constraint in a LP problem

Question

I am trying to solve following LP problem \begin{align} &\min_x –c^\top x \\ \text{s.t.} & \sum_{i=1}^M I(-a_i x\leq b) \geq m \\ & \sum_{i=1}^N x_i =1 \\ & x_i\geq 0 \end{align} where $m<M$, $x, a_i^\top\in\Re^{N\times1}$ and the indicator function $I(\cdot)$ is defined by \begin{equation*} \left\{\begin{aligned} I(\cdot)=1,&\quad \text{if}~ -a_i x\leq b \\ I(\cdot)=0,&\quad \text{if}~ -a_i x> b \end{aligned}\right. \end{equation*} For the indicator function, if matrix $a\in\Re^{M\times N}$, it means there are at least $m$ rows of matrix $a$ that satisfy inequality constraint $-a_i x\leq b$..... Hmm…. My mind got stuck here.

Is there any way to involve this indicator function in the optimization as a constraint?

Answer 1

It's possible to do with a mixed-integer linear program: just add the constraint $$-a_i x \le b + A(1-y_i)$$ where $y_1, y_2, \dots, y_M$ all take values in $\{0,1\}$, and $A$ is a large constant bigger than any possible value of $-a_i x$. Whenever $-a_i x > b$, $y_i$ will be forced to equal $0$. Now you can replace $$\sum_{i=1}^M I(-a_i x \le b) \ge m$$ with $$\sum_{i=1}^M y_i \ge m.$$

It's not possible to do without any kind of integer variables, because $I(\cdot)$ lets you simulate having integer variables around. For example, instead of defining $x \in \{0,1\}$, we can define $y \in [0,1]$ and $x = I(y \ge \frac12)$, which is equivalent.