# Linearizing objective function with variables inside an indicator function

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.

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$$.
• Thanks for the help! Do these two sets of inequality come in addition to the big-M constraint I wrote in the question? And I assume that ϵ is a small number? Do the bars on top and under $x_{j}$ on the right-hand side have special meaning? – Pierre Apr 4 at 18:43
• The first constraint replaces yours. The second one enforces the converse that $w_i=0 \implies v_i < \sum_j x_j z_{i,j}$. Yes, $\epsilon$ is a small positive constant. The bars indicate upper or lower bounds. I had assumed $z_{i,j} \ge 0$; if not, my big-M values will need adjusting. – RobPratt Apr 4 at 19:40
• @anoopyadav, yes, that expression plays the role of $M$ but is a small upper bound that is based on the problem data rather than just an arbitrary number. – RobPratt Apr 5 at 13:12
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).