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?
Best Answer
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.