## Wednesday, June 21, 2017

### Minimizing the k-th largest x

Minimizing the largest $$x_i$$ is an easy exercise in LP modeling:
 \bbox[lightcyan,10px,border:3px solid darkblue] { \begin{align} \min\>& z\\ & z \ge x_i \end{align}}
This is sometimes called MINIMAX.

What about minimizing the $$k^{\text{th}}$$ largest value? Here is one possible MIP formulation:

 \bbox[lightcyan,10px,border:3px solid darkblue] { \begin{align} \min\>& z\\ & z \ge x_i - \delta_i M\\ & \sum_i \delta_i = k-1\\ & \delta_i \in \{0,1\} \end{align}}

I.e., we have $$k-1$$ exceptions on the constraint $$z \ge x_i$$. The objective will make sure the exceptions are the largest $$x_i$$.  We should think long and hard about making the big-M’s as small as possible. If you have no clue about proper bounds on $$x_i$$ one could use indicator constraints.

Interestingly, minimizing the sum of the $$k$$ largest can be modeled as a pure LP (1) :

 \bbox[lightcyan,10px,border:3px solid darkblue] { \begin{align} \min\>& \sum_i v_i + k\cdot q\\ & v_i \ge x_i - q\\ &v_i \ge 0 \\ &q \text{ free } \end{align}}
You almost would think there is an LP formulation for minimizing the $$k^{\text{th}}$$ largest value. I don't see it however.
##### References
1. Comment by Michael Grant in http://orinanobworld.blogspot.se/2015/08/optimizingpartoftheobjectivefunction-ii.html.