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.