Maximising average of decision variables : mixed integer programming

Question

I am trying to linearise a model I came up with for this problem:
I have $n$ binary decision variables $x_i$ , each assosiated with a revenue $c_i$.
The profit will be either the weighted average of these : $\frac{\sum_{i=1}^n{x_ic_i}}{\sum_i^n{x_i}}$ or if I chose to keep as 1's , more or equal than 10 of them , the weighted average of the 10 most cheap: $\frac{\sum_{i=1}^n{c_iz_i} }{10}$ where $z_i=1 \iff $ it is in the 10 cheapest.
So one could say that the objective is : $$maximize \quad \frac{\sum_{i=1}^n{c_iz_i} }{\min(10, \sum_{i=1}^n x_i)}$$ This is definitely not a linear objective.
I was wondering if there is a stanard methodology for such problems. I found in wikipaideia something like ''fraction linear programming" but I have constraints in the form $z_i\leq x_i$ that do not follow the form that's suggested.

Answer 1

I assume that there is something in the model that might compel you to select more than 10 items even if they do not contribute to the objective function, since otherwise you could just add a constraint limiting you to 10 items. You can do this as a mixed integer linear program using some additional binary binary variables, and assuming you can come up with an a priori upper bound $S$ for your objective function.

For each $x_i$ we introduce a companion binary variable $z_i$ indicating whether it counts toward the objective function. We add the constraints $$z_i \le x_i$$ (don't count it if you didn't pick it) and $$\sum_i z_i \le 10$$ (count at most 10 terms). To enforce the requirement that the selected terms with lowest $c_i$ are the ones counted, define index sets $K_j = \lbrace i : c_i < c_j \rbrace$ and add the constraints $$\sum_{i\in K_j} x_i \le 9 + (\vert K_j\vert - 9 ) \cdot (1 - z_j).$$ If $j$ is not counted in the objective ($z_j = 0$), this has no effect. If $j$ is counted, this prevents selecting more than 9 lower value terms, meaning $j$ is within the 10 lowest value terms selected.

That leaves us with the task of linearizing the objective function. We introduce binary variables $t_1,\dots,t_{10}$ with the constraints $$\sum_{k=1}^{10} t_k = 1$$ and $$\sum_i z_i = t_1 + 2t_2 + \dots + 10t_{10}.$$ The combined effect is that $t_k = 1$ if and only if $k$ items count toward the objective.

Finally, we introduce nonnegative (continuous) variables $u_1,\dots,u_{10}$ and rewrite the objective as maximizing $\sum_k u_k.$ The defining constraints are $$u_k \le S\cdot t_k$$ and $$u_k \le \frac{\sum_i c_i \cdot z_i}{k}.$$ If $k$ items are chosen ($t_k = 1$), the solver will set $u_k = (\sum_i c_i \cdot z_i)/k,$ the average contribution of the selected items. If a different number of items are selected, $t_k = 0 \implies u_k = 0.$