7
$\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$
1
  • $\begingroup$ Definitely need binary variables to get this done. $\endgroup$
    – David
    Commented Apr 6, 2017 at 5:55

1 Answer 1

10
$\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$
2
  • $\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
    Commented Apr 6, 2017 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$ Commented Apr 6, 2017 at 13:57

You must log in to answer this question.

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