5
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Pierre Apr 4 at 18:43
  • $\begingroup$ 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. $\endgroup$ – RobPratt Apr 4 at 19:40
  • $\begingroup$ Can we just replace the entire bracket with M? $\endgroup$ – anoop Apr 5 at 7:31
  • $\begingroup$ @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. $\endgroup$ – RobPratt Apr 5 at 13:12
3
$\begingroup$

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).

| improve this answer | |
$\endgroup$

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.