3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Definitely need binary variables to get this done. $\endgroup$ – David Apr 6 '17 at 5:55
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, one more question, by introducing a binary variable y into the optimisation, is the LP no longer a convex optimisation? $\endgroup$ – Stephen Ge Apr 6 '17 at 6:25
  • $\begingroup$ Not really, no; you could think of the feasible region as consisting of disjoint convex sets, one for each value of $y$. But mixed integer linear programs are a class of their own; there's plenty of techniques people developed specific to them. $\endgroup$ – Misha Lavrov Apr 6 '17 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.