Linearizing objective function with variables inside an indicator function

Question

I am working on a problem in which I am trying to maximize the average of a variable only for the data that meet a certain condition with a constraint on the number of data that meet this condition. I am actually interested in constructing this condition.

Mathematically, my problem can be formulated as follows \begin{align}\max &\quad \frac{\sum_{i}y_{i}w_{i}}{\sum_{i}w_{i}}\\\text{s.t.}&\quad\sum_{i}w_{i} = n\end{align} where the $w_{i} = I(v_{i} \ge \sum_{j} x_{j} z_{ij})$ represent the condition. I want to optimize with respect to the $x_{j}$ variables. $v_{i}$, $y_{i}$ and $z_{ij}$ are available data.

My question is then: is it possible to linearize this problem for solving as a linear program? If not, do you have any suggestion to tackle this problem?

I've tried actually adding the $w_{i}$ as variables in the program with the constraint $$v_{i} - M \ge \sum_{j} x_{j} z_{ij} - Mw_{i}$$ with $M$ a value larger than the maximum of $v_{i}$. But it seems to result in a unbounded problem, although I am unsure why.

It is also worth noting that the constraint $\sum_{i}w_{i} = n$ could be relaxed as an inequality one.

Thank you for your help.

Answer 1

The usual big-M approach would impose two sets of inequalities: \begin{align} \sum_j x_j z_{i,j}-v_i &\le \left(\sum_j \overline{x}_j z_{i,j}-v_i\right)(1-w_i)\\ v_i+\epsilon-\sum_j x_j z_{i,j}&\le \left(v_i+\epsilon-\sum_j \underline{x}_j z_{i,j}\right)w_i \end{align} To linearize the objective function, replace the denominator with $n$.

Answer 2

Since Rob pointed out how to linearize the definition of the indicator variables, I'll focus on your objective, which is nonlinear. If you stick with the equality constraint $\sum_i w_i =n$, you can just replace the denominator in the objective with $n$ and the objective is linear. If, as is suggested in your question, you change the constraint to $\sum_i w_i \le n$ (or $\sum_i w_i \ge n$), then the objective function becomes a sticking point. Depending on the size of $n$ and the (unspecified) number of values of index $i$, your best bet might be to solve a sequence of problems where the "budget" constraint is $\sum_i w_i = k$ and $k$ is 1, then 2, ... then $n$ (or counts down to $n$ in the $\ge$ case).